首页 > 代码库 > BZOJ4589 Hard Nim(快速沃尔什变换模板)
BZOJ4589 Hard Nim(快速沃尔什变换模板)
终于抽出时间来学了学,比FFT不知道好写到哪里去。
#include <cstdio> typedef long long ll; const int N=65536,p=1e9+7; int k,m,n,a[N],pi[N]; bool pr(int x) {for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1;} ll pw(ll a,int b) {ll r=1; for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p; return r;} void fwt(int *a,ll f) { for(int i=1,x,y;i<n;i<<=1) for(int j=0;j<n;j+=i<<1) for(int k=0;k<i;k++) x=a[j+k],y=a[j+k+i],a[j+k]=(x+y)*f%p,a[j+k+i]=(x-y+p)*f%p; } int main() { for(int i=2;i<50001;i++) if(pr(i)) pi[i]=1; while(~scanf("%d%d",&k,&m)) { for(n=1;n<=m;n<<=1); for(int i=0;i<=m;i++) a[i]=pi[i]; for(int i=m+1;i<n;i++) a[i]=0; fwt(a,1); for(int i=0;i<n;i++) a[i]=pw(a[i],k); fwt(a,500000004),printf("%d\n",a[0]); } return 0; }
BZOJ4589 Hard Nim(快速沃尔什变换模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。