TopCoder SRM518 Div1 1000 Nim

题意:

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

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

定义卷积C=A*B,Cn=∑_i,j [i^j=n]*A_i*B_j,则答案为[x⁰]A^k,其中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=(x₁,y₁),B=(x₂,y₂),则A*B=(x₁*x₂+y₁*y₂,x₁*y₂+x₂*y₁)

设x=(x₁,x₂),此时dwt(x)=(x₁-x₂,x₁+x₂)

dwt(A)*dwt(B)=((x₁-y₁)*(x₂-y₂),(x₁+y₁)*(x₂+y₂))=dwt(A*B)

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

dwt(x)=(dwt(x₁)-dwt(x₂),dwt(x₁)+dwt(x₂))

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

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

解方程y₁=dwt(x₁)-dwt(x₂),y₂=dwt(x₁)+dwt(x₂)

解得:idwt(y)=(idwt((y₁+y₂)/2),idwt((y₂-y₁)/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];
		}
};