zoj 3874 Permutation Graph （cdq分治+NTT）

分类：数学

分治NTT算法

因为做做题学会了NTT ，比FFT的精度高了很多，，收货很大。/*code by islandsy1=a[0]+a[1]x^1+a[2]x^2…..a[n]x^ny2=b[0]+b[1]x^1+b[2]x^2…..b[m]x^my=y1*y2; 在O(nlgn)的复杂度求出y的系数*/#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<iostream>#include<map>#include<vector>#include<algorithm>#include<stdlib.h>#include<set>#include<ctime>#include<cmath>using namespace std;typedef long long LL;const int mmax = 1<<17;const int mod = 786433;const int g = 11; //原根LL quick_mod(LL a,LL b){LL ans=1;for(;b;b/=2){if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;}int rev(int x,int r) //蝴蝶操作{int ans=0;for(int i=0; i<r; i++){if(x&(1<<i)){ans+=1<<(r-i-1);}}return ans;}void NTT(int n,LL A[],int on) // 长度为N (2的次数){int r=0;for(;; r++){if((1<<r)==n)break;}for(int i=0; i<n; i++){int tmp=rev(i,r);if(i<tmp)swap(A[i],A[tmp]);}for(int s=1; s<=r; s++){int m=1<<s;LL wn=quick_mod(g,(mod-1)/m);for(int k=0; k<n; k+=m){LL w=1;for(int j=0; j<m/2; j++){LL t,u;t=w*(A[k+j+m/2]%mod)%mod;u=A[k+j]%mod;A[k+j]=(u+t)%mod;A[k+j+m/2]=((u-t)%mod+mod)%mod;w=w*wn%mod;}}}if(on==-1){for(int i=1;i<n/2;i++)swap(A[i],A[n-i]);LL inv=quick_mod(n,mod-2);for(int i=0;i<n;i++)A[i]=A[i]%mod*inv%mod;}}LL A[mmax+10],B[mmax+10];LL dp[mmax+10];LL jie[mmax+10];void cdq(int l,int r){if(l==r){dp[l]=jie[l]-dp[l];dp[l]=(dp[l]%mod+mod)%mod;return ;}int mid=(l+r)>>1;cdq(l,mid);int n=r-l+1;for(int i=0,j=l;i<n;i++,j++){if(j<=mid)A[i]=dp[l+i];elseA[i]=0;}for(int i=0;i<n;i++)B[i]=jie[i+1];NTT(n,A,1);NTT(n,B,1);for(int i=0;i<n;i++)A[i]=A[i]*B[i]%mod;NTT(n,A,-1);for(int i=r,j=n-2;i>mid;i–,j–){LL tmp=A[j];dp[i]+=tmp;dp[i]=(dp[i]%mod+mod)%mod;}cdq(mid+1,r);}void pre(){jie[0]=1;for(int i=1;i<mmax;i++)jie[i]=jie[i-1]*i%mod;int n=1;while(n<=mmax) n<<=1;n/=2;memset(dp,0,sizeof dp);cdq(1,n);}int c[mmax+10];int main(){pre();int T;cin>>T;while(T–){int n,m;scanf("%d %d",&n,&m);LL ans=1;while(m–){int cnt;scanf("%d",&cnt);for(int i=0;i<cnt;i++)scanf("%d",&c[i]);sort(c,c+cnt);bool fg=1;for(int i=1;i<cnt;i++)if(c[i]!=c[i-1]+1){fg=0;break;}if(!fg)ans=0;else{ans*=dp[cnt];ans%=mod;}}printf("%lld\n",ans);}return 0;}

上一篇快速数论变换模板(NTT)

顶0踩0

积极的人在每一次忧患中都看到一个机会，

相关文章：

你感兴趣的文章：

标签云：