传送门(Problem E)
题目描述得很麻烦，但是实际上是给定一个正整数矩阵$$A_{n*n}$$，问是否存在两个向量$$X_{1..n}$$, $$B_{1..n}$$使得\( A*X^T = B^T \) 并且B向量的元素全是整数，而X向量的元素不全是整数。$$1 \leq n \leq 100$$, $$\vert A_{ij} \vert \leq 100$$
- 如果A不满秩，那么显然存在。
-
如果A满秩，有两种思路
- 求A的逆矩阵，看矩阵里有没有非实数，如果有，那么存在这两个向量，否则不存在。具体原因是：$$A*X^T = B^T$$ –> $$X^T = A^{-1}B^T$$。而B里必须是整数，如果A的逆阵也全是整数的话，X只能取整数。但是这个方法需要判断一个逆阵里是否全是整数，而高斯消元的过程中，元素的增长总是指数级的，很容易构造到数据使得精度不够。除非使用Java的BigInteger用分数表示，否则真的是非常繁杂。
- 根据cramer法则上面提到的线性方程组的第i组解为\[\frac{det(A_i)}{det(A)}\]其中$$det(A_i)$$表示的是将A矩阵的第i列换成$$B^T$$以后的列向量。由B向量的任意性，这个$$det(A_i)$$可以取任意的整数，这样如果$$det(A)$$不是1或者-1的话，必然可以使得某一个$$X_i$$不是整数。所以归根到底，只要判断$$det(A)$$是不是1或者-1就行了。当然这个即使是实数运算，也比方法1要好得多，但是还是不够靠谱。A的元素是整数，行列式也肯定是整数，那么可以选取若干个素数，求出行列式对这些素数取模以后是不是1或-1，如果验证了好几个素数以后结果还是一致，那么就是正确的。如果担心正确性，可以使取的素数之积达到$$100^{100}$$，这样值域和定义域的大小一致，基本就不会出错了。
#include
#include
#include
#include
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int N = 105;
int n;
int a[N][N], b[N][N];
int inverse(ll a, int Mod) {
ll res = 1;
for (int b = Mod - 2; b; b >>= 1) {
if (b & 1) res = res * a % Mod;
a = a * a % Mod;
}
return res;
}
bool ok(int Mod) {
rep (i, n) rep (j, n) b[i][j] = (a[i][j] % Mod + Mod) % Mod;
ll det = 1;
rep (i, n) {
for (int j = i + 1; j < n && !b[i][i]; j++) {
if (b[j][i]) {
for (int k = i; k < n; k++)
swap(b[i][k], b[j][k]);
det = (-det + Mod) % Mod;
break;
}
}
if (!b[i][i]) return 0;
det = (det * b[i][i] % Mod + Mod) % Mod;
ll inv = inverse(b[i][i], Mod);
for (int j = i + 1; j < n; j++) {
if (b[j][i]) {
ll mul = inv * b[j][i] % Mod;
for (int k = i; k < n; k++) {
b[j][k] = ((b[j][k] - mul * b[i][k]) % Mod + Mod) % Mod;
}
}
}
}
return (det == 1) || (det == Mod - 1);
}
int main() {
scanf("%d", &n);
rep (i, n) rep (j, n) scanf("%d", &a[i][j]);
if (ok(1000000007) && ok(1000000009) && ok(1000003)) {
puts("Death");
} else {
puts("Power of magic saves lives");
}
}
的方案数，结果对1e+7取模。
