pdf版题面 在线提交（需要权限）
题目
问题描述
蒻滋滋是一名实力强大的 OIer 。不久前，他在滋滋国国家队选拔赛过程中突发神题过敏综合征，情况危急，但他坚持回到考场，边做手术边比赛，最终仅以微弱差距不敌某交通工具获得全场第二。为此还被授予了感动滋滋国 OIer 荣誉称号。
在校园里，蒻滋滋是一个乐于助人的模范学长。 whx 小学妹经常来向蒻滋滋请教。前不久， whx 在学习区分奇数和偶数时遇到了困难，便来找蒻滋滋寻求帮助，蒻滋滋不仅和她详细讲解了区分奇数偶数的方法，还一时兴起，给 whx 普及了多项式和行列式的相关知识。
善于思考的 whx 小学妹立马提出了一个问题：给一个$N \times N$的矩阵$A$，$A$的每个元素都是一个整系数多元多项式，现在求出这个矩阵的行列式$|A|$，显然$|A|$也是一个多元多项式。 whx 想知道，把$|A|$合并同类项之后，是否每一项前的系数都是偶数呢？
行列式的定义：$|A| = \sum_{\sigma \in S_N} {\rm sgn}(\sigma) \prod_{i = 1}^{N} A_{i, \sigma(i)}$，其中$S_N$是$N$的所有排列组成的集合，当排列$\sigma$的逆序对数目为偶数时${\rm sgn}(\sigma) = 1$，否则${\rm sgn}(\sigma) = -1$。
输入格式
第一行一个正整数$T$表示数据组数，对于每组数据：
第一行一个正整数$N$表示行列式的阶数。
接下来$N$行，每行$N$个用空格隔开的字符串表示矩阵$A$。
一个字符串表示一个多元多项式，具体表示方法如下：
多项式的每一项用一个包含小写字母或数字的字符串表示，不同的项之间仅用一个‘+’隔开，对于包含数字的项，只可能是常数项“0”或“1”，非常数项是一个小写字母串（不包含数字），一个小写字母出现次数代表了他的次数，项可能重复出现，所以其系数就是出现次数，一个多项式至少有一项（零多项式表示为“0”）。
例如$2ax^2 + pq + 1$可以表示为“1+xax+pq+axx”。
输出格式
对于每组数据输出一行一个单词“Yes”表示每一项前系数都是偶数，“No”表示存在一项的系数不是偶数。
样例输入1
4
1
p+p
2
xx+1 0
0 x
3
x y z
x y z
x y z
orz qaq tat
3
a+b b+c c+a
b+c c+a a+b
ab+bc ac+bc ab+ac
点击这里下载
样例输出1
Yes
No
Yes
Yes
点击这里下载
样例数据1解释
第一个行列式为$2p$，第二个行列式为$x^3 + x$，第三个行列式为$0$，第四个行列式为$2a^2b^2 + 2a^2c^2 + 2b^2c^2 - 2a^2bc - 2ab^2c - 2abc^2$。
样例输入2
点击这里下载
样例输出2
点击这里下载
数据范围与约定
令$len_{i, j}$表示$A_{i, j}$输入字符串的长度。
对于$20\%$的数据：$N \leq 4, len_{i, j} \leq 20$
对于$20\%$的数据：$N \leq 20, A_{i, j} \in \{0, 1, x, 1 + x\}$
对于$100\%$的数据：$T \leq 20, N \leq 50, len_{i, j} \leq 100$，变量个数不超过$26$（所有小写字母）。
题解
（稍后再补）
代码
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
| #include <cstdio> #include <cstring> #include <cstdlib> #include <ctime> #include <cctype> #include <algorithm> using namespace std; #define MAXN 60 #define MAXL 110 const int MOD = 0x2000035; inline int getrand() { int s = 0; while ((s ^ MOD) > s) s = (s << 1) | (rand() & 1); return (s ^ MOD); } int T; int n; char str[MAXN][MAXN][MAXL]; int data[MAXN][MAXN]; int value[26]; int mul(int a, int b) { int s = 0; while (b) { if (b & 1) s ^= a; a <<= 1; if (a > (a ^ MOD)) a ^= MOD; b >>= 1; } return s; } int getvalue(int x, int y) { int len = strlen(str[x][y]); char *s = str[x][y]; int r = 0, t = 1; for (int i = 0; i < len; i++) { char c = s[i]; if (c == '+') { r ^= t; t = 1; } else if (isalpha(c)) t = mul(t, value[c - 'a']); else t = c - '0'; } return r; } bool gauss() { for (int i = 0; i < n; i++) { int k = -1; for (int j = i; j < n; j++) if (data[j][i]) { k = j; break; } if (k == -1) return true; if (i != k) for (int j = 0; j < n; j++) swap(data[i][j], data[k][j]); for (int j = i + 1; j < n; j++) if (data[j][i]) { int ls = data[j][i]; for (int k = 0; k < n; k++) data[j][k] = mul(data[j][k], data[i][i]) ^ mul(data[i][k], ls); } } return false; } int main() { freopen("rzz.in", "r", stdin); freopen("rzz.out", "w", stdout); srand(time(0)); scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { scanf("%s", str[i][j]); str[i][j][strlen(str[i][j]) + 1] = 0; str[i][j][strlen(str[i][j])] = '+'; } int test; for (test = 0; test < 5; test++) { for (int i = 0; i < 26; i++) value[i] = getrand(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) data[i][j] = getvalue(i, j); if (!gauss()) break; } if (test < 5) printf("No\n"); else printf("Yes\n"); } return 0; }
|
