本文主要是介绍【ZOJ 3874】Permutation Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
浙江省赛题。当时赛后听说是NTT+CDQ震惊了两个词一个都没有听说过。
现在突然想起来这个题，回来一看也并不是那么的不可做。比赛的时候还在打表找规律233~
首先可以想到，因为逆序对都要连一条边，因此所有的对于任意一个部分都是下表连续的，否则答案就为0。
若下表连续的，则可以想到答案只与长度有关。
不妨设dp[i]为长度为i的连续下表的方案数，则可以得到
dp[i] = i! - sigma(dp[i - k] * k!)，其中 1<= k < i
简单解释一下就是说，若1-i连续，则必须全是在同一个块中
考虑不合法的情况，不妨设最后一个块为k个连续的数，则需要减去的方案为dp[i - k] * k!
后面是卷积，可以用ntt计算。
说起来NTT的模板还没有补，有空补。
再有如果直接一项一项地算也是n^2logn的复杂度爆炸。
因此用cdq分治来优化一下就好了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;#define lson l,mid
#define rson mid + 1,r
#define root 1,n
#define Mid int mid = (l + r) >> 1const int N = 1 << 18;
const int mod = 786433;
const int G = 10;int dp[N];
int fac[N];
int x1[N << 1],x2[N << 1],tmp[N << 1];
int tn;
int Pow(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;
}
int rev(int x){int res = 0;for(int i = 0 ; i < tn ; i ++){if(x & 1) res += 1 << tn - i - 1;x >>= 1;}return res;
}
void ntt(int A[],int n,int op){for(int i = 0 ; i < n ; i ++) tmp[ rev(i) ] = A[i];for(int i = 0 ; i < n ; i ++) A[i] = tmp[i];for(int i = 1 ; (1 << i) <= n ; i ++){int m = 1 << i;int wn;if(op == 1) wn = Pow(G,(mod - 1) / m);else wn = Pow(G,(mod - 1) - (mod - 1) / m);for(int k = 0 ; k < n ; k += m){int w = 1,u,t;for(int j = 0 ; j < m / 2 ; j ++){u = A[k + j];t = 1ll * w * A[k + j + m / 2] % mod;A[k + j] = (u + t) % mod;A[k + j + m / 2] = (u - t + mod) % mod;w = 1ll * w * wn % mod;}}}if(op == -1){int Inv = Pow(n,mod - 2);for(int i = 0 ; i < n ; i ++)A[i] = 1ll * A[i] * Inv % mod;}
}
void cdq(int l,int r){if(l > r) return;if(l == r){dp[l] = (dp[l] + fac[l]) % mod;return;}Mid;cdq(lson);int len = 1;tn = 0;while(len < (mid - l + 1) * 2)len <<= 1,tn ++;for(int i = l ; i <= mid ; i ++) x1[i - l] = dp[i];for(int i = mid - l + 1 ; i < len ; i ++) x1[i] = 0;for(int i = 0 ; i < len ; i ++) x2[i] = fac[i];ntt(x1,len,1);ntt(x2,len,1);for(int i = 0 ; i < len ; i ++)x1[i] = 1ll * x1[i] * x2[i] % mod;ntt(x1,len,-1);for(int i = mid + 1 ; i <= r ; i ++){dp[i] += (mod - x1[i - l]) % mod;dp[i] %= mod;}cdq(rson);
}
void init(){int n = 100002;fac[0] = 1;for(int i = 1 ; i <= n ; i ++)fac[i] = 1ll * fac[i - 1] * i % mod;cdq(root);
}
void solve(){int n,m;scanf("%d%d",&n,&m);int c,l,r,x;int ret = 1;for(int i = 1 ; i <= m ; i ++){l = n + 1,r = -1;scanf("%d",&c);for(int j = 0 ; j < c ; j ++){scanf("%d",&x);l = min(l,x);r = max(r,x);}ret = 1ll * ret * dp[c] % mod;if(r - l + 1 != c) ret = 0;}printf("%d\n",ret);
}
int main()
{init();int _;scanf("%d",&_);while(_--) solve();return 0;
}这篇关于【ZOJ 3874】Permutation Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
