phpstudy配置网站,优秀网站设计赏析怎么写,泌阳专业网站建设,商标注册号查询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 原理并不知道 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) #includebits/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;
} View Code 转载于:https://www.cnblogs.com/19992147orz/p/8284565.html
