ZOJ3874 Permutation Graph

Time Limit: 2 Seconds Memory Limit: 65536 KB

Edward has a permutation {a₁, a₂, … a_n}. He finds that if he connects each pair (a_i, a_j) such that i < j and a_i > a_j, he will get a graph.

For example, if the permutation is {2, 3, 1, 4}, then 1 and 2 are connected and 1 and 3 are connected.

Edward lost his permutation, but he does know the connected components of the corresponding graph. He wants to know how many permutations will result in the same connected components.

Note that two vertices u, v belong to the same connected component if there exists a sequence of vertices starting with u and ending with v such that every two subsequent vertices in the sequence are connected by an edge.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers n, m (1 ≤ m ≤ n ≤ 100000), indicating the length of the permutation and the number of connected components in the graph.

Each of the following m lines contains an integer c_i which denotes the size of i-th connected component, followed by c_i distinct integers v_i,1, v_i,2, … v_{i,c_i} which denotes the connected component (1 ≤ c_i, v_i,1, v_i,2, … v_{i,c_i} ≤ n).

It is guaranteed that every number will appear in exact one connected component and c₁ + c₂ + … + c_m = n.

Output

For each case, output the answer modulo 786433.

Sample Input

Sample Output

1
3

Hint

For the second case, the three permutations is: {2, 3, 1, 4}, {3, 2, 1, 4}, {3, 1, 2, 4}.

Author: LIN, Xi
Source: The 12th Zhejiang Provincial Collegiate Programming Contest

动态规划分治NTT优化

随意脑补一下可以发现构成连通块的数排序后一定是连续+1递增的一串，不然它们中肯定有数连到别的地方去。

设f[i]表示大小恰好为i的连通块的方案数首先列出一个简单粗暴的方程：

　$ f[i]=sum_{j=1}^{i} A_{j}^{j} * f[i-j] $

　$ A_{j}^{j}=j!$

复杂度$O(n^2)$

注意到右边构成了一个卷积的形式，且每个f都只由比它小的f计算得到。

于是可以愉快地用分治NTT优化DP

（前置技能：CDQ分治）

分治NTT理解了以后其实挺简单的，利用CDQ分治计算整个序列，当处理一个区间时，该区间的前一半已经被算完了，只需要把前一半的项卷积一下，答案累加到下标对应的后一半位置去，如此递归分治即可。

注意NTT的数组空间要开到(mid-l+1)的两倍。刚开始想当然觉得for(N=1,len=0;N<=m;N<<=1)等价，实际上这样做的话N会停在某个比size大，比2*size小的2的幂上

786433的原根是10 ←不知为什么记成11，调了半天

  1 /*by SilverN*/
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 #define LL long long
  9 using namespace std;
 10 const int mod=786433;
 11 const int G=10;
 12 const int mxn=100010;
 13 int read(){
 14     int x=0,f=1;char ch=getchar();
 15     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 16     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 17     return x*f;
 18 }
 19 LL fac[mxn];
 20 void init(){
 21     fac[0]=1;
 22     for(int i=1;i<mxn;i++)fac[i]=(LL)fac[i-1]*i%mod;
 23     return;
 24 }
 25 LL ksm(LL a,LL k){
 26     int res=1;
 27     while(k){
 28         if(k&1)res=(LL)res*a%mod;
 29         a=(LL)a*a%mod;
 30         k>>=1;
 31     }
 32     return res;
 33 }
 34 LL a[mxn<<1],b[mxn<<1];
 35 int N,len,rev[mxn<<1];
 36 void NTT(LL *a,int flag){
 37     for(int i=0;i<N;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
 38     for(int i=1;i<N;i<<=1){
 39         int p=i<<1;
 40         LL gn=ksm(G,(flag==1)?(mod-1)/p:(mod-1)-(mod-1)/p);
 41         for(int j=0;j<N;j+=p){
 42             LL g=1;
 43             for(int k=0;k<i;k++,g=(LL)g*gn%mod){
 44                 LL x=a[j+k],y=g*a[j+k+i]%mod;
 45                 a[j+k]=(x+y)%mod;
 46                 a[j+k+i]=(x-y+mod)%mod;
 47             }
 48         }
 49     }
 50     if(flag==-1){
 51         LL INV=ksm(N,mod-2);
 52         for(int i=0;i<N;i++)a[i]=(LL)a[i]*INV%mod;
 53     }
 54     return;
 55 }
 56 LL f[mxn];
 57 void solve(int l,int r){
 58     if(l==r){
 59         f[l]=((fac[l]-f[l])%mod+mod)%mod;
 60         //当l==r时，比l小的f全都算完了，可以得出f[l]=fac[l]-f[l] 
 61         return;
 62     }
 63     int i,j,mid=(l+r)>>1;
 64     solve(l,mid);//先算前一半 
 65     int m=(mid-l+1)<<1;//空间开两倍 
 66     for(N=1,len=0;N<=m;N<<=1)len++;
 67     for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
 68     for(i=0;i<N;i++)a[i]=b[i]=0;
 69     for(i=l;i<=mid;i++)//为了节省空间，将每一项左移l位计算
 70         a[i-l]=f[i];
 71     for(i=l;i<=r;i++)b[i-l]=fac[i-l];
 72     //
 73     NTT(a,1);NTT(b,1);
 74     for(i=0;i<N;i++)a[i]=(LL)a[i]*b[i]%mod;
 75     NTT(a,-1);
 76     for(i=mid+1;i<=r;i++){//将贡献累加到右半边 
 77         (f[i]+=a[i-l])%=mod;
 78     }
 79     solve(mid+1,r);
 80     return;
 81 }
 82 int n;
 83 int num[mxn];
 84 bool check(int x){
 85     sort(num+1,num+x+1);
 86     for(int i=2;i<=x;i++){
 87         if(num[i]!=num[i-1]+1)return 0;
 88     }
 89     return 1;
 90 }
 91 int main(){
 92     int i,j;
 93     init();
 94     f[0]=1;
 95     solve(1,100000);
 96     int T=read(),m;
 97     while(T--){
 98         n=read();m=read();
 99         bool flag=1;
100         LL ans=1;
101         for(i=1;i<=m;i++){
102             int sz=read();
103             for(j=1;j<=sz;j++)num[j]=read();
104             if(!check(sz))flag=0;
105             ans=(ans*f[sz])%mod;
106         }
107         if(!flag)puts("0");
108         else printf("%lld
",ans);
109     }
110     return 0;
111 }