ShinriiTin's Blog - 博主是sb

TopCoder SRM518 Div1 1000 Nim

题意:

      有k(k<=109)堆石子,每堆石子的数量都是不大于L(L<=50000)的质数,

问有多少种初始状态是先手必败状态,mod 1000000007

 

定义卷积C=A*B,Cn=∑i,j [i^j=n]*Ai*Bj,则答案为[x0]Ak,其中Ai=[i为质数]

 

Fast Walsh Transform

 

考虑一种Transformation u(f),满足u(A)*u(B)=u(A*B),

并且存在u(f)的Inverse Transformation v(f),满足v(u(f))=f

 

假设向量x的长度为n

当n为1时,显然u(x)=x,因为0^0=0,满足u(A)*u(B)=u(A*B)

当n为2时,设A=(x1,y1),B=(x2,y2),则A*B=(x1*x2+y1*y2,x1*y2+x2*y1)

设x=(x1,x2),此时dwt(x)=(x1-x2,x1+x2)

dwt(A)*dwt(B)=((x1-y1)*(x2-y2),(x1+y1)*(x2+y2))=dwt(A*B)

对于n为大于等于2的2的整次幂,x=(x1,x2),x1和x2的长度为n/2

dwt(x)=(dwt(x1)-dwt(x2),dwt(x1)+dwt(x2))

 

令y=dwt(x),考虑其逆变换idwt(y)=x,当n=1时同理idwt(y)=y

当n为大于等于2的2的整次幂,y=(y1,y2),

解方程y1=dwt(x1)-dwt(x2),y2=dwt(x1)+dwt(x2)

解得:idwt(y)=(idwt((y1+y2)/2),idwt((y2-y1)/2))

 

虽然我并不清楚这是怎么想出来的,但是在知道有这个变换的情况下,

理解它的正确性还是比较容易的,而且它的形式也很优美呢。

 

class Nim{
	public:
		static const int MAXN=(1<<17)+5;
		static const int Mod=1e9+7;
		typedef long long ll;

		inline ll qpow(ll x,int k,int M){
			ll ans=1;
			for(;k;x=x*x%M,k>>=1)
				if(k&1)ans=ans*x%M;
			return ans;
		}

		int r2;

		int a[MAXN];

		void dwt(int l,int r){
			if(l==r)return;
			int mid=(l+r)>>1,len=r-mid;
			dwt(l,mid),dwt(mid+1,r);
			for(int i=l;i<=mid;++i){
				int x=a[i],y=a[i+len];
				a[i]=(x-y+Mod)%Mod;
				a[i+len]=(x+y)%Mod;
			}
		}

		void idwt(int l,int r){
			if(l==r)return;
			int mid=(l+r)>>1,len=r-mid;
			for(int i=l;i<=mid;++i){
				int x=1ll*a[i]*r2%Mod;
				int y=1ll*a[i+len]*r2%Mod;
				a[i]=(x+y)%Mod;
				a[i+len]=(y+Mod-x)%Mod;
			}
			idwt(l,mid),idwt(mid+1,r);
		}

		bool ban[MAXN];

		int p[MAXN],tot;

		inline void get_prime(int n){
			ban[1]=1;
			for(int i=2;i<=n;++i){
				if(!ban[i])p[++tot]=i;
				for(int j=1;j<=tot;++j){
					if(1ll*i*p[j]>n)break;
					ban[i*p[j]]=1;
				if(!(i%p[j]))break;
				}
			}
		}

		inline int count(int K,int L){
			r2=qpow(2,Mod-2,Mod);
			get_prime(L);
			for(int i=1;i<=L;++i)a[i]=!ban[i];
			int l=1<<16;
			dwt(0,l-1);
			for(int i=0;i<l;++i)
			a[i]=qpow(a[i],K,Mod);
			idwt(0,l-1);
			return a[0];
		}
};