2019.7.3模拟 七星连珠（行列式+随机+k进制FWT）

2019.7.3模拟 七星连珠（行列式+随机+k进制FWT）

题目大意：

给一个(n*n)的矩阵，对于所有排列p，记录(a[i][p[i]])的k进制下不进位加法的结果，问所有被记录过的数。

(n<=50,p=2、3,0<=a[i][j]<p^7)

题解：

又是排列，不妨考虑行列式：

(|A|=sum_{p是排列}(-1)^{p的逆序对个数} prod A[i][p[i]])

这里的A是一个集合幂级数，×定义为k进制不进位加法卷积。

假设我们直接做高斯消元求行列式，发现由于((-1)^？)次方，可能导致本来≠0而加起来为0，所以需要随机一个系数作为集合幂级数的系数。

带着这么个集合幂级数去高斯消元显然不太行，假设p=2，不妨先FWT，这样卷积就变成了点积，并且点积不同位之间没有影响，所以可以先枚举是哪一位，再消元。

这样的话复杂度是(O(n^3*p^7))。

那么问题就在于如何做p进制的FWT。

发现FWT的本质就是构造一个可逆的转移矩阵，这里转移矩阵需要满足做出来点积后是k进制不进位加法，也就是k的循环溢出，那么不妨直接用FFT的单位复数根去完成这个东西。

即转移矩阵(b[i][j]=w_k^{ij})，逆FWT就是(w_k^{-ij}/k)。

(w_k)可以取FFT的((cos(2*pi/k),sin(2*pi/k)*i))，也可以NTT那样取一个(p|(mo-1))的质数mo，然后用(原根^{(mo-1)/k})

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("n")
#define db long double
using namespace std;int rand(int x, int y) {return ((ll) RAND_MAX * rand() + rand()) % (y - x + 1) + x;
}const int mo = 1e9 + 9;ll ksm(ll x, ll y) {ll s = 1;for(; y; y /= 2, x = x * x % mo)if(y & 1) s = s * x % mo;return s;
}int num, n, k, a[51][51];
ll w[3];
void fwt(ll *a, int n, int f) {ll v = ksm(ksm(13, (mo - 1) / k), f == 1 ? 1 : mo - 2);w[0] = 1; ff(i, 1, k) w[i] = w[i - 1] * v % mo;for(int h = 1; h < n; h *= k) {for(int j = 0; j < n; j += k * h) {ff(i, 0, h) {ll c[3]; ff(u, 0, k) c[u] = 0;ff(u, 0, k) ff(v, 0, k) c[v] += a[i + j + h * u] * w[u * v % k] % mo;ff(u, 0, k) a[i + j + h * u] = c[u] % mo;}}}if(f == -1) {v = ksm(n, mo - 2);ff(i, 0, n) a[i] = a[i] * v % mo;}
}const int N = 2187 + 5;int m;
ll b[51][51][N], c[N], d[51][51];ll solve(ll a[][51]) {ll s = 1;fo(i, 1, n) {int u = i;fo(j, i, n) if(a[j][i]) { u = j; break;}if(i != u) {fo(j, 1, n) swap(a[i][j], a[u][j]);s *= -1;}ll ni = ksm(a[i][i], mo - 2);fo(j, i + 1, n) if(a[j][i]) {ll v = -a[j][i] * ni % mo;fo(k, 1, n) a[j][k] = (a[j][k] + a[i][k] * v) % mo;}}fo(i, 1, n) s = s * a[i][i] % mo;return s;
}int main() {srand(time (0) + clock());freopen("astrology.in", "r", stdin);freopen("astrology.out", "w", stdout);scanf("%d %d %d", &num, &n, &k);m = 1; fo(i, 1, 7) m = m * k;fo(i, 1, n) fo(j, 1, n) scanf("%d", &a[i][j]);fo(i, 1, n) fo(j, 1, n) {b[i][j][a[i][j]] = rand(1, mo - 1);fwt(b[i][j], m, 1);}solve(d);ff(u, 0, m) {fo(i, 1, n) fo(j, 1, n) d[i][j] = b[i][j][u];c[u] = solve(d);}fwt(c, m, -1);ff(i, 0, m) if(c[i]) pp("%d ", i);
}

转载于:.html