题目描述
Claris和NanoApe在玩石子游戏，他们有n堆石子，规则如下：
1. Claris和NanoApe两个人轮流拿石子，Claris先拿。
2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。
不同的初始局面，决定了最终的获胜者，有些局面下先拿的Claris会赢，其余的局面Claris会负。
Claris很好奇，如果这n堆石子满足每堆石子的初始数量是不超过m的质数，而且他们都会按照最优策略玩游戏，那么NanoApe能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对10^9+7取模的值。
输入
输入文件包含多组数据，以EOF为结尾。
对于每组数据：
共一行两个正整数n和m。
每组数据有1<=n<=10^9, 2<=m<=50000。
不超过80组数据。
输出
每组数据输出一个数，表示答案
样例输入
3 7 4 13
样例输出
6 120
题解
FWT裸题
Nim游戏后手必胜条件：每堆石子数异或和为0。
那么设f[i]表示异或和为i的方案数，显然这是一个异或规则下的卷积（卷积求幂）
所以使用FWT，每个数转化后求对应的幂次，再求逆FWT即为答案。
#include#include #define N 70000typedef long long ll;const ll mod = 1000000007 , inv = 500000004;int np[N] , prime[N] , tot;ll a[N];ll pow(ll x , int y){ ll ans = 1; while(y) { if(y & 1) ans = ans * x % mod; x = x * x % mod , y >>= 1; } return ans;}void fwt(int len){ int i , j , k; ll t; for(i = 2 ; i <= len ; i <<= 1) for(j = 0 ; j < len ; j += i) for(k = j ; k < j + (i >> 1) ; k ++ ) t = a[k] , a[k] = (a[k] + a[k + (i >> 1)]) % mod , a[k + (i >> 1)] = (t - a[k + (i >> 1)] + mod) % mod;}void ufwt(int len){ int i , j , k; ll t; for(i = len ; i >= 2 ; i >>= 1) for(j = 0 ; j < len ; j += i) for(k = j ; k < j + (i >> 1) ; k ++ ) t = a[k] , a[k] = (a[k] + a[k + (i >> 1)]) * inv % mod , a[k + (i >> 1)] = (t - a[k + (i >> 1)] + mod) * inv % mod;}int main(){ int n , m , i , j , len; for(i = 2 ; i <= 50000 ; i ++ ) { if(!np[i]) prime[++tot] = i; for(j = 1 ; j <= tot && i * prime[j] <= 50000 ; j ++ ) { np[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } while(~scanf("%d%d" , &n , &m)) { memset(a , 0 , sizeof(a)); for(i = 1 ; i <= tot && prime[i] <= m ; i ++ ) a[prime[i]] = 1; for(len = 1 ; len <= m ; len <<= 1); fwt(len); for(i = 0 ; i < len ; i ++ ) a[i] = pow(a[i] , n); ufwt(len); printf("%lld\n" , a[0]); } return 0;}