bzoj 4589: Hard Nim 异或规则下的多项式乘法

45 阅读 0 评论 30 点赞

我是靠谱客的博主怡然啤酒，最近开发中收集的这篇文章主要介绍bzoj 4589: Hard Nim 异或规则下的多项式乘法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

定义(a$b)i = Σaj * bi^j ，那么题目相当于求A^N的第0项，其中Ai=[i为质数且i<=m]。

~~显然我们可以用快速幂+分治乘做到N^1.59logN，光荣TLE。~~

UPD：后来发现这是fwt是Nlog^2N的好像能过。

和普通多项式乘法一样，我们寻找一种变换trans(a)，使得trans(a$b)=trans(a)*trans(b)，这里有(X*Y)i=Xi*Yi。只要能O(NlogN)转化和复原就能解决这个问题，先来看a,b含有两个数的情况。

a(x,y)，b(z,w)。trans(a)=(x-y,x+y)，trans(b)=(z-w,z+w)，那么：

trans(a$b)=trans((xz+yw,xw+yz))=(xz+yw-xw-yz,xz+yw+xw+yz)，trans(a)*trans(b)=((x-y)(z-w),(x+y)(z+w))，显然两者相同。

对于一般情况，定义a=(a1,a2)，表示ai=a1i(i<n/2)或者a2(i-n/2)(i>n/2)，有trans(a)=(trans(a1)-trans(a2),trans(a1)+trans(a2))。这个和上面一样用a,b展开即可证明。

复原就是每一步都反着来。然后递归实现即可。不过这道题目非递归还是很简单的应该会快不少。

UPD：本质就是fwt。

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define mod 1000000007
#define inv 500000004
#define N 70005
using namespace std;
int n,m,cnt,a[N],c[N]; bool vis[N];
int ksm(int x,int y){
int t=1; for (; y; y>>=1,x=(ll)x*x%mod) if (y&1) t=(ll)t*x%mod;
return t;
}
void trs(int l,int r){
if (l==r) return; int mid=(l+r)>>1,i,j,x;
trs(l,mid); trs(mid+1,r);
for (i=l,j=mid+1; i<=mid; i++,j++){
x=(a[i]+a[j])%mod;
a[i]=(a[i]-a[j]+mod)%mod; a[j]=x;
}
}
void rsto(int l,int r){
if (l==r) return; int mid=(l+r)>>1,i,j,x;
for (i=l,j=mid+1; i<=mid; i++,j++){
x=(ll)(a[j]-a[i]+mod)*inv%mod;
a[i]=(ll)(a[i]+a[j])*inv%mod; a[j]=x;
}
rsto(l,mid); rsto(mid+1,r);
}
int main(){
int i,j;
for (i=2; i<=50000; i++){
if (!vis[i]) c[++cnt]=i;
for (j=1; j<=cnt && i*c[j]<=50000; j++){
vis[i*c[j]]=1;
if (!(i%c[j])) break;
}
}
c[cnt+1]=50001;
while (~scanf("%d%d",&n,&m)){
memset(a,0,sizeof(a));
for (i=1; c[i]<=m; i++) a[c[i]]=1;
j=1; while (j<=m) j<<=1; j--;
trs(0,j);
for (i=0; i<=j; i++) a[i]=ksm(a[i],n);
rsto(0,j);
printf("%dn",a[0]);
}
return 0;
}

by lych

2016.5.17