bzoj 4589: Hard Nim
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2106 Solved: 1126
[Submit][Status][Discuss]
Description
Claris和NanoApe在玩石子游戏，他们有n堆石子，规则如下：
- Claris和NanoApe两个人轮流拿石子，Claris先拿。
- 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。
不同的初始局面，决定了最终的获胜者，有些局面下先拿的Claris会赢，其余的局面Claris会负。
Claris很好奇，如果这n堆石子满足每堆石子的初始数量是不超过m的质数，而且他们都会按照最优策略玩游戏，那么NanoApe能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对10^9+7取模的值。
Input
输入文件包含多组数据，以EOF为结尾。
对于每组数据：
共一行两个正整数n和m。
每组数据有1<=n<=10^9, 2<=m<=50000。
不超过80组数据。
Output
Sample Input
3 7
4 13
Sample Output
6
120
这个博弈显然 是NIM游戏不过是想让我们求出有多少局面使得 石子的异或和为0 这样才能保证后手获胜。
(注意读题 都是质数 我读成第m个质数了。。这导致我对题意理解存在偏差。。
那么这道题就很显然了 设f[i][j]前i堆棋子异或和为j的方案数。显然可以快速幂优化。显然这类似于卷积的形式 FWT异或优化即可。
(我是不会告诉你我读错题都能想出来这些东西的。。
当然这道题 有一个trick我们不需要再快速幂中使用FWT 而是在FWT中使用快速幂。
考虑FWT吧A这个多项式变成A' 我们想要在异或运算下求出(A^n)
可以考虑FWT转换完之后 对于 AB=C 这里运算被定义为卷积异或运算。而我们FWT做的是 A->A' B->B' (A'cdot B'=C')这里·的运算为点积。
可以发现上述(A^n)相当于 n个A做*运算我们把这n个都变成FWT进行点积运算 最后再转换回来即可得到结果。
所以FWT套快速幂 要比快速幂套FWT快的多。总复杂度mlogm*T(数据组数。
注意：
FFT,NTT只适用于被套于快速幂之中。因为NTT的原理和FWT的原理可以说并不相同。
int n,m,top,maxx=50000;
int p[MAXN],v[MAXN],lim;
ll f[MAXN];
inline void prepare()
{
for(int i=2;i<=maxx;++i)
{
if(!v[i])v[i]=p[++top]=i;
for(int j=1;j<=top;++j)
{
if(maxx/i<p[j])break;
v[i*p[j]]=p[j];
if(v[i]==p[j])break;
}
}
}
inline int fast_pow(ll b,ll p)
{
ll cnt=1;
while(p)
{
if(p&1)cnt=cnt*b%mod;
b=b*b%mod;
p=p>>1;
}
return cnt;
}
inline void FWT_xor(ll *a,int op)
{
for(int len=2;len<=lim;len=len<<1)
{
int mid=len>>1;
for(int j=0;j<lim;j+=len)
for(int i=0;i<mid;++i)
{
f[i+j]=(f[i+j]+f[i+j+mid])%mod;
f[i+j+mid]=(f[i+j]-f[i+j+mid]-f[i+j+mid])%mod;
f[i+j]=f[i+j]*op%mod;f[i+j+mid]=f[i+j+mid]*op%mod;
}
}
}
int main()
{
freopen("1.in","r",stdin);
prepare();
while(gt(n)==1)
{
gt(m);
memset(f,0,sizeof(f));
for(int i=1;i<=top&&p[i]<=m;++i)++f[p[i]];
lim=1;while(lim<=m)lim=lim<<1;
FWT_xor(f,1);
for(int i=0;i<lim;++i)f[i]=fast_pow(f[i],n);
FWT_xor(f,fast_pow(2,mod-2));
printf("%lld
",(f[0]+mod)%mod);
}
return 0;
}