记录编号	277787	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] 花样游戏	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.226 s
提交时间	2016-07-06 15:03:38	内存使用	2.01 MiB

#include<stdio.h>
#define maxn 200010
#define mod 1000000007
int k,l,m,inv;
bool vis[maxn];
int p[maxn],f[maxn];
int POW(int x,int y){
	for(int z=1;;x=1ll*x*x%mod,y>>=1)
		if(y&1)z=1ll*z*x%mod;
		else if(!y)return z;	
}
void get_p(){
	for(int i=2;i<=l;++i){
		if(!vis[i])p[++p[0]]=i;
		for(int j=1;j<=p[0]&&i*p[j]<=l;++j){
			vis[i*p[j]]=1;
			if(!(i%p[j]))break;
		}
	}
}
void FWT(int*o,int n,int flag){
	for(int i=2;i<=n;i<<=1)
		for(int j=0;j<n;j+=i)
			for(int k=0,p=i>>1;k<p;++k){
				int x=o[j+k],y=o[j+k+p];
				o[j+k]=1ll*(x+y)*flag%mod;
				o[j+k+p]=1ll*(x-y+mod)*flag%mod;
			}
}
int main(){
	freopen("srmnim.in","r",stdin);
	freopen("srmnim.out","w",stdout);
	scanf("%d%d",&k,&l);
	get_p();
	for(m=1;m<=l;m<<=1);
	for(int i=1;i<=p[0];++i)f[p[i]]=1;
	FWT(f,m,1);
	for(int i=0;i<m;++i)f[i]=POW(f[i],k);
	FWT(f,m,POW(2,mod-2));
	printf("%d",f[0]);
}