BZOJ3456

http://www.lydsy.com/JudgeOnline/problem.php?id=3456

 

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int mod=1004535809,maxn=1<<18|1;int p[maxn],gn[233];int n;int fac[maxn],inv[maxn],tp[maxn];inline int fp(int a,int b){	int res=1;	while(b){		if(b&1)res=1ll*res*a%mod;		a=1ll*a*a%mod;b>>=1;	}	return res;}inline void init(){	for(register int i=0;i<=23;++i)gn[i]=fp(3,(mod-1)/(1<<(i+1)));	fac[0]=1;for(register int i=1;i<=n+1;++i)fac[i]=1ll*fac[i-1]*i%mod;	inv[1]=1;for(register int i=2;i<=n+1;++i)inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;	inv[0]=1;for(register int i=1;i<=n+1;++i)inv[i]=1ll*inv[i]*inv[i-1]%mod;	for(register int i=0;i<=n+1;++i)tp[i]=fp(2,(1ll*i*(i-1)/2)%(mod-1));}struct poly{	int a[maxn],n;	poly(){memset(a,0,sizeof(a));}	inline int &operator[](const int x){return a[x];}	inline void ntt(int d,int f){		for(register int i=0;i
         
          
           >1]>>1)^((i&1)<<(lg2-1)); A.ntt(d,1);B.ntt(d,1); for(register int i=0;i
           
            >1); register int d=1,lg2=0;for(d=1;d<=(deg<<1);d<<=1)++lg2; for(register int i=0;i
            
             >1]>>1)^((i&1)<<(lg2-1)); for(register int i=0;i
             
              
               >1;i