题目链接

题解

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

F=PnF=Pn

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

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

代码

#include 
    
     #include 
     
      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
      
       >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