fwt
原理并不知道
nim游戲石子異或和=0后手贏
那么也就是求a[1]^a[2]^...^a[n]=0的方案數
這個和bzoj3992一樣可以dp
dp[i][j]表示前i個數異或和為j的方案數 dp[0][0] = 1
dp[i][j] = dp[i - 1][k] * a[p] p ^ k = j a[p] = 0 / 1 表示有沒有p這個數
這個東西也不能矩陣快速冪?
但是我們有一個叫fwt的東西
能夠求c = a @ b @是一種運算 -----> c[i] = a[j] * b[k] i = j ^ k
那么每次轉移就是fwt了
由于轉移的形式一樣 那么就可以快速冪 并且由于fwt運算并不會向fft那樣下標多出來一些東西 也就不用算循環卷積
直接fwt后每個數pow一下 再ifwt就行了
復雜度O(n log n + n log m)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 70005; const ll P = 1000000007; int n, m, len; ll inv; ll a[N]; int p[N], mark[N]; ll power(ll x, ll t) {ll ret = 1;for(; t; t >>= 1, x = x * x % P) if(t & 1) ret = ret * x % P;return ret; } void fwt(ll *a, int n) {for(int l = 2; l <= n; l <<= 1){ int m = l >> 1;for(int i = 0; i < n; i += l) for(int k = 0; k < (l >> 1); ++k){ll x = a[i + k], y = a[i + k + m];a[i + k] = (x + y) % P;a[i + k + m] = ((x - y) % P + P) % P;}} } void ifwt(ll *a, int n) {for(int l = n; l >= 2; l >>= 1){int m = l >> 1;for(int i = 0; i < n; i += l)for(int k = 0; k < m; ++k){ll x = a[i + k], y = a[i + m + k];a[i + k] = (x + y) % P * inv % P;a[i + m + k] = ((x - y) % P + P) % P * inv % P;}} } int main() {inv = power(2, P - 2);for(int i = 2; i <= 50000; ++i) {if(!mark[i]) p[++p[0]] = i;for(int j = 1; j <= p[0] && i * p[j] <= 50000; ++j) {mark[i * p[j]] = 1;if(i % p[j] == 0) break;}}while(scanf("%d%d", &n, &m) != EOF) {memset(a, 0, sizeof(a));for(int i = 1; i <= p[0] && p[i] <= m; ++i) a[p[i]] = 1;for(len = 1; len <= m; len <<= 1);fwt(a, len);for(int i = 0; i < len; ++i) a[i] = power(a[i], n);ifwt(a, len);printf("%lld\n", a[0]);}return 0; }
?
