求矩阵的所有行和列的乘积均为 (k) 的方案数。要求矩阵是 (n imes n) 的，由整数组成（可负）。(T le 2 imes 10^5,n le 5 imes 10^6)，每组数据的 (k) 已知，质因数不超过二次。
首先符号的贡献显然是独立的，(k=1) 的贡献显然是 (2^{(n-1)^2})（考虑前 ((n-1) imes (n-1)) 随便填，用剩下一行一列来调整）。那么剩下我们要做的就是计算出正整数的贡献。
考虑到 (k = 31 imes 37^2) 与 (k = 2 imes 3^2) 等价。具体地说，答案只与 (k) 的一次质因数和二次质因数的个数有关。而质因数之间又是独立的。
首先考虑一次质因数的情况。那么我们要做的就是在 (n imes n) 的网格中每行每列都只填一个 1 的方案数。这是个组合数学的入门题，答案是 (n!)
然后考虑二次质因数的情况。那么我们要做的就是在 (n imes n) 的网格中填若干 (1) 或 (2)，使得每行每列的和为 (2)。题解中有一个转化为图论问题用生成函数多项式求逆求解的方法，并不会。
考虑最后一列填的什么。如果填的是 (2)，那么删去最后一列和那一行能够转化成子问题；如果填的是两个 (1)，那么如果这两行的另一个 (1) 恰好是在同一列，那么合并并挪到最下面能够与最右边列是一个 (2) 的情况一一对应；如果不同，将那两行合并并放到最下面，能够与最右边列是两个 (1) 的情况映射，注意这里的删除合并是二对一的关系（左上右下或左下右上）。
设 (f(n)) 表示 (n imes n) 矩阵最右边列为一个 (2) 的方案数；(g(n)) 表示 (n imes n) 矩阵最右边列是两个 (1) 的方案数。那么转移为：
关键代码
inline void init() {
f[1] = 0, g[1] = 1;
for (register int i = 2; i <= 5e6; ++i) {
g[i] = 1ll * i * (g[i - 1] + f[i - 1]) % P;
f[i] = (1ll * i * (i - 1) / 2) % P * ((f[i - 1] << 1) + g[i - 1]) % P;
}
}
int main() {
...
init();
int _; read(_);
while (_--) {
int n; read(n);
ll ans = quickpow(jie[n], can1) * quickpow((f[n] + g[n]) % P, can2) % P;
ans = ans * quickpow(2, 1ll * (n - 1) * (n - 1) % (P - 1)) % P;
printf("%lld
", (ans % P + P) % P);
}
return 0;
}