高斯消元法。
其实就是线性代数里解线性方程组，但这题还要求等式两边mod7。
解向量中xi的取值范围是[3,9]，共有m个方程，判断是否有解，如果有解，要判断是否有唯一解。
这题一开始走了弯路，想象以前解普通线性方程组那样用浮点数依次选列主元后化成上三角来求解。但发现在这题mod7条件下，行不通。
后来发现可以用一个很差的时间复杂度完全使用整数进行处理。。。由于数据规模不大，发现这样是可行的。每次消元处理后都也要注意各种取模，不然很易RE。
反正最后就是各种暴力。。。就过了。。。
|
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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include<cstdio> #include<cstring> int n,m,d[300]; int ab[300][301],t[301]; char s[4],e[4]; int gcd(int a,int b) { if(a%b==0) return b; return gcd(b,a%b); } int lcm(int a,int b) { if(!a||!b) return 0; return a*b/gcd(a,b); } int chk(char s[]) { if(!strcmp(s,"MON")) return 1; if(!strcmp(s,"TUE")) return 2; if(!strcmp(s,"WED")) return 3; if(!strcmp(s,"THU")) return 4; if(!strcmp(s,"FRI")) return 5; if(!strcmp(s,"SAT")) return 6; return 7; } inline int calc(int a,int b) { a=(a%7+7)%7; b=(b%7+7)%7; for(int d=3;d<=9;d++) if(a*d%7==b) return d; return -1; } void solve() { int i,j,k,l,o,p; memset(ab,0,sizeof ab); for(i=0;i<m;i++) { scanf("%d%s%s",&j,s,e); k=chk(s); l=chk(e); ab[i][n]=l-k+1; while(j--) { scanf("%d",&k); ab[i][k-1]++; } } for(i=0;i<m;i++) for(j=0;j<=n;j++) ab[i][j]%=7; for(i=l=0;i<n;i++) { for(j=l;j<m&&!ab[j][i];j++); if(j==m) continue; if(j>l) { memcpy(t,ab[j],sizeof t); memcpy(ab[j],ab[l],sizeof t); memcpy(ab[l],t,sizeof t); } for(j=l+1;j<m;j++) { if(!ab[j][i]) continue; p=lcm(ab[j][i],ab[l][i])/ab[j][i]; for(o=i;o<=n;o++) ab[j][o]*=p; p=ab[j][i]/ab[l][i]; for(o=i;o<=n;o++) { ab[j][o]-=ab[l][o]*p; ab[j][o]%=7; } } l++; } for(i=m-1;i>-1;i--) { for(j=0;j<=n&&!ab[i][j];j++); if(j==n) { puts("Inconsistent data."); return; } } memset(d,-1,sizeof d); for(i=l-1;i>-1;i--) { for(j=0;j<n&&!ab[i][j];j++); if(j==n) continue; for(k=j+1;k<n&&!ab[i][k];k++); if(k<n) { puts("Multiple solutions."); return; } d[j]=calc(ab[i][j],ab[i][n]); for(k=i-1;k>-1;k--) { if(!ab[k][j]) continue; p=lcm(ab[i][j],ab[k][j])/ab[k][j]; for(o=0;o<=n;o++) ab[k][o]*=p; p=ab[k][j]/ab[i][j]; for(o=0;o<=n;o++) { ab[k][o]-=ab[i][o]*p; ab[k][o]%=7; } } } for(i=0;i<n;i++) if(d[i]==-1) { puts("Multiple solutions."); return; } for(i=0;i<n-1;i++) printf("%d ",d[i]); printf("%d\n",d[n-1]); } int main() { while(~scanf("%d%d",&n,&m)&&n) solve(); return 0; } |