- #include#include#include#include#include using namespace std;
- const int N = 305;
- inline int read() {
- char c = getchar();
- int x = 0,
- f = 1;
- while (c < '0' || c > '9') {
- if (c == ' - ') f = -1;
- c = getchar();
- }
- while (c >= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- typedef int Matrix[N][N];
- int n,
- m,
- P = 7;
- char s1[5],
- s2[5];
- Matrix a;
- int mp[300];
- inline int num(char * s) {
- if (s[0] == 'T') return s[1] == 'U' ? 1 : 3;
- else if (s[0] == 'S') return s[1] == 'A' ? 5 : 6;
- else return mp[s[0]];
- }
- int inv[10];
- void iniInv() {
- inv[1] = 1;
- for (int i = 2; i <= P; i++) inv[i] = ( - P / i * inv[P % i] % P P) % P;
- }
- int now,
- pivot[N];
- void Gauss() {
- now = 1;
- for (int i = 1; i <= n; i++) {
- int j = now;
- while (j <= m && !a[j][i]) j++;
- if (j == m + 1) continue;
- //printf("hi %d %d %d\n",i,now,j);
- if (j != now) for (int k = 1; k <= n + 1; k++) swap(a[now][k], a[j][k]);
- for (int j = now + 1; j <= m; j++) if (a[j][i]) { //printf("jjj %d\n",j);
- int t = a[j][i] * inv[a[now][i]] % P; //printf("t %d\n",t);
- for (int k = i; k <= n + 1; k++) a[j][k] = (a[j][k] - a[now][k] * t % P P) % P;
- }
- pivot[i] = now; //printf("pivot %d %d\n",i,pivot[i]);
- now++;
- }
- //printf("now %d\n",now);now--;
- for (int i = now; i >= 1; i--) {
- int pi = pivot[i],
- pj;
- for (int j = now; j > i; j--) pj = pivot[j],
- a[pi][n + 1] = (a[pi][n + 1] - a[pi][pj] * a[pj][n + 1] % P P) % P;
- a[pi][n + 1] = a[pi][n + 1] * inv[a[pi][i]] % P;
- }
- }
- void solve() {
- //printf("now %d\n",now);
- //for(int i=1;i<=m;i++)
- //for(int j=1;j<=n+1;j++) printf("%d%c",a[i][j],j==n+1?'\n':' ');
- for (int i = 1; i <= m; i++) if (a[i][n + 1]) {
- int f = 0;
- for (int j = 1; j <= n; j++) if (a[i][j]) {
- f = 1;
- break;
- }
- if (f == 0) {
- puts("Inconsistent data.");
- return;
- }
- }
- if (now "Multiple solutions.");
- return;
- }
- for (int i = 1; i <= n; i++) printf("%d%c", a[i][n + 1] < 3 ? a[i][n + 1] + P: a[i][n + 1], i == n ? '\n': '');
- }
- inline void ini() {
- memset(a, 0, sizeof(a));
- memset(pivot, 0, sizeof(pivot));
- }
- int main() {
- //freopen("in","r",stdin);
- mp['M'] = 0;
- mp['W'] = 2;
- mp['F'] = 4;
- iniInv();
- while (true) {
- ini();
- n = read();
- m = read();
- if (n == 0 && m == 0) break;
- for (int i = 1; i <= m; i++) {
- int k = read();
- scanf("%s%s", s1, s2);
- a[i][n + 1] = (num(s2) - num(s1) + 1 + P) % P;
- while (k--) a[i][read()]++;
- for (int j = 1; j <= n + 1; j++) a[i][j] %= P;
- //printf("a %d\n",i);
- //for(int j=1;j<=n+1;j++) printf("%d%c",a[i][j],j==n+1?'\n':' ');
- }
- Gauss();
- solve();
- }
- }
来源: http://www.bubuko.com/infodetail-1949087.html