两题都是高斯消元法。（也都1A了^^）
两题题面都很有意思，分别描述了确定有唯一解的模运算线性方程组，唯一解是因为前者是范德蒙行列式，后者则是给定了满秩系数矩阵。
两题都没有太大难度的，代码也相近。
2065的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include<cstdio> #include<cstring> int n,p,ab[100][100],t[100]; char s[100]; int gcd(int a,int b) { if(a%b==0) return b; return gcd(b,a%b); } void init() { int i,j,k,l; n=strlen(s);; memset(ab,0,sizeof ab); for(i=0,k=1;i<n;i++,k++) { ab[i][0]=1; for(j=1;j<n;j++) ab[i][j]=ab[i][j-1]*k%p; if(s[i]=='*') ab[i][n]=0; else ab[i][n]=s[i]-'a'+1; } } int calc(int a,int b) { int i; if(a<0) a+=p; if(b<0) b+=p; for(i=0;i<p;i++) if(a*i%p==b) return i; } void solve() { int i,j,k,l,m,g; for(i=0;i<n;i++) { for(j=i+1;j<n&&!ab[j][i];j++); if(j!=i+1) { memcpy(t,ab[i],sizeof t); memcpy(ab[i],ab[j],sizeof t); memcpy(ab[j],t,sizeof t); } for(j=i+1;j<n;j++) { if(!ab[j][i]) continue; g=gcd(ab[i][i],ab[j][i]); l=ab[i][i]/g; m=ab[j][i]/g; for(k=0;k<=n;k++) ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p; } } for(i=n-1;i;i--) { for(j=i-1;j>-1;j--) { if(!ab[j][i]) continue; g=gcd(ab[i][i],ab[j][i]); l=ab[i][i]/g; m=ab[j][i]/g; for(k=0;k<=n;k++) ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%p; } } for(i=0;i<n-1;i++) printf("%d ",calc(ab[i][i],ab[i][n])); printf("%d\n",calc(ab[i][i],ab[i][n])); } int main() { scanf("%*d"); while(~scanf("%d%s",&p,s)) { init(); solve(); } return 0; } |
1166的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include<cstdio> #include<cstring> int ab[9][10],t[10],tl,tn[10]; int d[]={1,1,0,1,0,0,0,0,0,0, 1,1,1,0,1,0,0,0,0,0, 0,1,1,0,0,1,0,0,0,0, 1,0,0,1,1,0,1,0,0,0, 1,0,1,0,1,0,1,0,1,0, 0,0,1,0,1,1,0,0,1,0, 0,0,0,1,0,0,1,1,0,0, 0,0,0,0,1,0,1,1,1,0, 0,0,0,0,0,1,0,1,1,0}; int gcd(int a,int b) { if(a%b==0) return b; return gcd(b,a%b); } int init() { int i,j,k,l; if(-1==scanf("%d",&k)) return 0; memcpy(ab,d,sizeof d); ab[0][9]=-k; for(i=1;i<9;i++) { scanf("%d",&k); ab[i][9]=-k; } return 1; } int calc(int a,int b) { int i; if(a<0) a+=4; if(b<0) b+=4; for(i=0;i<4;i++) if(i*a%4==b) return i; } void solve() { int i,j,k,l,m,g; for(i=0;i<9;i++) { for(j=i;j<9&&!ab[j][i];j++); if(j!=i) { memcpy(t,ab[i],sizeof t); memcpy(ab[i],ab[j],sizeof t); memcpy(ab[j],t,sizeof t); } for(j=i+1;j<9;j++) { if(!ab[j][i]) continue; g=gcd(ab[i][i],ab[j][i]); l=ab[i][i]/g; m=ab[j][i]/g; for(k=0;k<10;k++) ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4; } } for(i=8;i;i--) { for(j=i-1;j>-1;j--) { if(!ab[j][i]) continue; g=gcd(ab[i][i],ab[j][i]); l=ab[i][i]/g; m=ab[j][i]/g; for(k=0;k<10;k++) ab[j][k]=(ab[j][k]*l-ab[i][k]*m)%4; } } for(i=tl=0;i<9;i++) { j=calc(ab[i][i],ab[i][9]); if(j) { t[tl]=i+1; tn[tl]=j; tl++; } } for(i=0;i<tl-1;i++) while(tn[i]--) printf("%d ",t[i]); while(--tn[i]) printf("%d ",t[i]); printf("%d\n",t[i]); } int main() { while(init()) solve(); return 0; } |
好久没来了……这几天都在看书+帮人折腾VPS。Linode用久了就以为主机商都该是这样的，现在算认识到很多产品还是良萎不齐的（而且还死贵……）