题目大意:
Claris 和 NanoApe 在玩石子游戏, 他们有 n 堆石子, 规则如下:
Claris 和 NanoApe 两个人轮流拿石子, Claris 先拿.
每次只能从一堆中取若干个, 可将一堆全取走, 但不可不取, 拿到最后 1 颗石子的人获胜.
不同的初始局面, 决定了最终的获胜者, 有些局面下先拿的 Claris 会赢, 其余的局面 Claris 会负.
Claris 很好奇, 如果这 n 堆石子满足每堆石子的初始数量是不超过 m 的质数, 而且他们都会按照最优策略玩游戏, 那么 NanoApe 能获胜的局面有多少种.
由于答案可能很大, 你只需要给出答案对 10^9+7 取模的值.
思路:
先手必败是所有的石子的 SG 函数值异或起来等于 0.
设 \(f_{i,j}\) 表示进行了第 \(i\) 堆石子, 异或和为 \(j\) 的方案数是多少, 实际上是一个异或卷积, 直接上 FWT 优化即可.
- /*=======================================
- * Author : ylsoi
- * Time : 2010.2.10
- * Problem : bzoj4589
- * E-mail : ylsoi@foxmail.com
- * ====================================*/
- #include<bits/stdc++.h>
- #define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
- #define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
- #define debug(x) cout<<#x<<"="<<x<<" "
- #define fi first
- #define se second
- #define mk make_pair
- #define pb push_back
- typedef long long ll;
- using namespace std;
- void File(){
- freopen("bzoj4589.in","r",stdin);
- freopen("bzoj4589.out","w",stdout);
- }
- template<typename T>void read(T &_){
- _=0; T f=1; char c=getchar();
- for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
- for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0');
- _*=f;
- }
- const int maxn=5e4+10;
- const ll mod=1e9+7;
- const ll inv2=(mod+1)/2;
- int n,m,lim;
- ll f[maxn<<1];
- int pm[maxn],tot;
- bool vis[maxn];
- void init_prime(){
- REP(i,2,5e4){
- if(!vis[i])pm[++tot]=i;
- REP(j,1,tot){
- if(i*pm[j]>5e4)break;
- vis[i*pm[j]]=1;
- if(i%pm[j]==0)break;
- }
- }
- }
- ll qpow(ll x,ll y){
- ll ret=1; x%=mod;
- while(y){
- if(y&1)ret=ret*x%mod;
- x=x*x%mod;
- y>>=1;
- }
- return ret;
- }
- void fwt(ll *A,int ty){
- for(int len=1;len<lim;len<<=1)
- for(int L=0;L<lim;L+=len<<1)
- REP(i,L,L+len-1){
- ll x=A[i],y=A[i+len];
- A[i]=(x+y)*(ty==1 ? 1 : inv2)%mod;
- A[i+len]=(x-y)*(ty==1 ? 1 : inv2)%mod;
- }
- }
- int main(){
- File();
- init_prime();
- while(~scanf("%d%d",&n,&m)){
- lim=1;
- while(lim<=m)lim<<=1;
- REP(i,0,lim-1)f[i]=0;
- REP(i,1,tot)if(pm[i]<=m)f[pm[i]]=1;
- else break;
- fwt(f,1);
- REP(i,0,lim-1)f[i]=qpow(f[i],n);
- fwt(f,-1);
- printf("%lld\n",(f[0]+mod)%mod);
- }
- return 0;
- }
[bzoj4589]Hard Nim--SG 函数 + FWT
来源: http://www.bubuko.com/infodetail-2949497.html