F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4589 >> 新人求助,Hard Nim那题本机AC提交WA
cx233666 @ 2018-10-18 20:06:05
[ Quote ] [ Edit ] [ Delete ] 1#
RT

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
int k=0;char ch=gt;
while(ch<'-')ch=gt;
while(ch>'-')k=k*10+ch-'0',ch=gt;
return k;
}
const int YL=1e9+7;
int pr[500005],np[500005],tot,a[200005],len,b[200005];
inline void add(int &x,int y){x+=y;if(x>=YL)x-=YL;}
inline void dec(int &x,int y){x-=y;if(x< 0)x+=YL;}
void fwt(int *a,int opt)
{
for(int st=2,m=1;st<=len;st<<=1,m<<=1)
for(int *p=a;p!=a+len;p+=st)
for(int k=0,x,y;k<m;++k)
x=p[k],y=p[k+m]
,p[k]=1ll*opt*(x+y)%YL,p[k+m]=1ll*opt*(x-y+YL)%YL;

}
void ksm(int n)
{
fwt(a,1);memset(b,0,sizeof b);b[0]=1;fwt(b,1);
while(n)
{
if(n&1)for(int i=0;i<len;++i)b[i]=1l*b[i]*a[i]%YL;
for(int i=0;i<len;++i)a[i]=1ll*a[i]*a[i]%YL;
n>>=1;
}
fwt(b,(YL+1)/2);
printf("%d\n",b[0]);
}
int main()
{
for(int i=2;i<=100000;++i)
{
if(!np[i])pr[++tot]=i;
for(int j=1;j<=tot&&i*pr[j]<=100000;++j)
{
np[i*pr[j]]=1;if(i%pr[j]==0)break;
}
}
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(a,0,sizeof a);
int i;
for(i=1;pr[i]<=m;++i)++a[pr[i]];
for(len=1;len<=pr[i-1];len<<=1);
ksm(n);
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back