BZOJ 4589 Hard Nim

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4589

题解

求F(0)F(0)，FF满足

F=PnF=Pn

其中P(i)=[i∈prime]P(i)=[i∈prime]，卷积为集合对称差卷积。

先线筛求出PP，FWT一下，对每个元素快速幂，最后FWT回去，输出F(0)F(0)。

代码

#include <cstdio>
#include <cstring>

const int maxn=280000;
const int mod=1000000007;
const int inv_2=500000004;

int p[maxn+10],prime[maxn+10],cnt,n;

int getprime()
{
  p[1]=1;
  for(int i=2; i<=maxn; ++i)
    {
      if(!p[i])
        {
          prime[++cnt]=i;
        }
      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)
        {
          p[i*prime[j]]=1;
          if(i%prime[j]==0)
            {
              break;
            }
        }
    }
  return 0;
}

int quickpow(int a,int b,int m)
{
  int res=1;
  while(b)
    {
      if(b&1)
        {
          res=1ll*res*a%m;
        }
      a=1ll*a*a%m;
      b>>=1;
    }
  return res;
}

int add(int a,int b,int m)
{
  int res=a+b;
  if(res>=m)
    {
      res-=m;
    }
  return res;
}

int minus(int a,int b,int m)
{
  int res=a-b;
  if(res<0)
    {
      res+=m;
    }
  return res;
}

int fwt_xor(int *s,int len,int op)
{
  for(int i=2; i<=len; i<<=1)
    {
      for(int j=0; j<len; j+=i)
        {
          for(int k=0; k<(i>>1); ++k)
            {
              int x=s[j+k],y=s[j+k+(i>>1)];
              s[j+k]=add(x,y,mod);
              s[j+k+(i>>1)]=minus(x,y,mod);
              if(op==-1)
                {
                  s[j+k]=1ll*s[j+k]*inv_2%mod;
                  s[j+k+(i>>1)]=1ll*s[j+k+(i>>1)]*inv_2%mod;
                }
            }
        }
    }
  return 0;
}

int getrev(int x)
{
  int res=1;
  while(x>=res)
    {
      res<<=1;
    }
  return res;
}

int a[maxn+10],m,k;

int main()
{
  getprime();
  while(scanf("%d%d",&k,&n)!=EOF)
    {
      m=getrev(n);
      memset(a,0,sizeof a);
      for(int i=1; i<=n; ++i)
        {
          if(!p[i])
            {
              a[i]=1;
            }
        }
      fwt_xor(a,m,1);
      for(int i=0; i<m; ++i)
        {
          a[i]=quickpow(a[i],k,mod);
        }
      fwt_xor(a,m,-1);
      printf("%d\n",a[0]);
    }
  return 0;
}