首页 > 编程学习 > 21年icpc上海区域赛B题Strange Permutations (容斥+生成函数)

题意: 求给定n的排列P,求满足对于任意i∈[1,n-1]满足 Q i + 1 ≠ P Q i Q_{i+1}\neq P_{Q_{i}} Qi+1=PQi的Q排列方案数。(n<=1e5)
Solution: 排列的图意义

\quad 直接看这个式子有点晕,看到排列可以从图意义入手。
我们设P,Q的图意义为: P Q i − > Q i + 1 P_{Q_{i}}->Q_{i+1} PQi>Qi+1,当然反过来也一样的(这个意义想了几天,被 i − > P i + 1 i->P_{i+1} i>Pi+1的固有套路给框柱了,意义是可以自定义的)。如果考虑i从1到n的话,连出来肯定是若干环,这个和 i − > P i i->P_{i} i>Pi的建图意义是一样的。
\quad 乱证一下:因为 P Q i P_{Q_i} PQi是个排列, Q i + 1 Q_{i+1} Qi+1也是个排列(先假设Q{n+1}有意义),把两个排列按照 Q i + 1 Q_{i+1} Qi+1大小排序,就转化成了 i − > P i i->P_i i>Pi
\quad 然后因为i只从1到n-1,那图是个哈密顿图(哈密顿路径)。因为只有n-1个点有出边,n-1个点有入边,且出入度至多为1,画画图得连出来是个哈密顿图。或者从上面连出来的环意义考虑,首先环是不合法的,因为有环就意味这每个点入出度都为1,显然不对,那还要联通,只能是哈密顿图了。
\quad 说了这么多就想证,图意义是哈密顿图。那问题转化成图上有n条禁边,求合法的哈密顿路径数量。禁边的可以设成(i,Pi)。
\quad 为什么这样设是对的呢,上面证了i->Pi的建图意义和 P Q i − > Q i + 1 ( 假设 Q n + 1 的意义是 Q 1 且 Q 1 不存在 ) P_{Q_{i}}->Q_{i+1}(假设Q_{n+1}的意义是Q_1且Q_1不存在) PQi>Qi+1(假设Qn+1的意义是Q1Q1不存在)等价,那反过来也是等价的。
直观点,我们列出 P Q i P_{Q_i} PQi Q i + 1 Q{i+1} Qi+1
P:3 4 1 2
Q:1 4 3 2
P Q i P_{Q_i} PQi:3 2 1 4
Q i + 1 Q_{i+1} Qi+1: 4 3 2 ?
根据上面的建图意义,这是合法的。
来组不合法的。
P:3 4 1 2
Q:1 3 4 2
P Q i P_{Q_i} PQi:3 2 1 4
Q i + 1 Q_{i+1} Qi+1:3 4 2 ?
3指向3不合法了,发现用 i − > P i i->P_i i>Pi与这个建图意义的禁边意义是相同的!于是就可以转成n条禁边(i,Pi)。而n条禁边组成了若干环,我们要选的是哈密顿回路,所以不能有环。
\quad 考虑容斥, f ( i ) f(i) f(i)表示钦定选i条禁边的哈密顿路径数,因为不能有环,所以对于禁边组成的若干环,每个环上的边都不能全取,则 a n s = ∑ i = 0 n − 1 ( − 1 ) i ∗ f ( i ) ans=\sum_{i=0}^{n-1}(-1)^i*f(i) ans=i=0n1(1)if(i)(这是二项式反演,但不是没有组合数的容斥系数!容斥系数在后面的多项式计算里体现出来了!所以最外层不用带组合数!!!)。
设每个环多项式为 g ( x ) = ∑ i = 0 s i z − 1 C ( s i z , i ) x i g(x) = \sum_{i=0}^{siz-1}C(siz,i)x^i g(x)=i=0siz1C(siz,i)xi,其中siz为环大小。
设 F = ∏ g j , f ( i ) = [ x i ] F 设F =\prod g_j, f(i)=[x^i]F F=gj,f(i)=[xi]F,即第i项的系数,F的计算用启发式合并算一下就可以了。
时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
这题难点还是在求解问题的转化上。搞清楚后,很容易。
(因为这题结合别的大佬们的题解理解了好久,把一些自己想错的问题都写了,所以比较长,还有一些证明和理解也是自己瞎想的,如有不对的话,还请读者留言区指正,感谢)

#defien int long long
const int N=1e5+5;
const int mod=998244353;
const double eps=1e-8;
const int MAXL = 60;
int n,k;
int a[N];
std::vector<int> G[N];
const int maxn = 6e6+10;
const int p = 998244353;
int Pow(int x,int d){
    int tans = 1;
    if(d == 0)return 1%p;
    int a = Pow(x,d/2);
    tans = 1ll*a*a%p;
    if(d%2)tans = 1ll*tans*x%p;
    return tans%p;
}
typedef vector<int> Poly;//多项式定义
int F1[maxn],F2[maxn];
int rev[maxn];
void NTT(int * A,int lim,int opt) {
    int i, j, k, m, gn, g, tmp;
    for(int i = 0; i < lim; ++i)rev[i] = (i & 1)*(lim >> 1) + (rev[i >> 1] >> 1);
    for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
    for(m = 2; m <= lim; m <<= 1) {
        k = m >> 1;
        gn = Pow(3,(p - 1) / m);
        for(i = 0; i < lim; i += m) {
            g = 1;
            for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
                tmp = 1ll * A[i + j + k] * g % p;
                A[i + j + k] = (A[i + j] - tmp + p) % p;
                A[i + j] = (A[i + j] + tmp) % p;
            }
        }
    }
    if(opt == -1){
        reverse(A+1,A+lim);
        int inv = Pow(lim,p-2);
        for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
    }
}
Poly operator + ( const Poly &A,const Poly &B){
    int n = A.size() , m = B.size();
    int siz = max(n,m);
    Poly C(siz,0);
    for(int i=0 ;i<siz ;i++){
        if( i <n && i < m) C[i] = (A[i] + B[i])%p;
        else if( i < n ) C[i] = A[i];
        else C[i] = B[i];
    }
    return C;
}
Poly mul(const Poly & A,const Poly & B){
    int n = A.size(),m = B.size();
    int siz = n + m - 1;
    Poly C(siz);
    if(siz < 64){//小于等于64项直接暴力算
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++)C[i+j] = (C[i+j] + 1LL*A[i]*B[j]%p)%p;
        }
        return C;
    }
    int fsiz = 1;
    while(fsiz <= siz)fsiz <<=1;
    for(int i = 0;i < fsiz;i++)F1[i] = F2[i] = 0;
    for(int i = 0;i < n;i++)F1[i] = A[i];
    for(int i = 0;i < m;i++)F2[i] = B[i];
    NTT(F1,fsiz,1);
    NTT(F2,fsiz,1);
    for(int i = 0;i < fsiz;i++)F1[i] = 1ll*F1[i]*F2[i]%p;
    NTT(F1,fsiz,-1);
    for(int i = 0;i < siz;i++){
        C[i] = F1[i];
    }
    return C;
}
int fac[N],ni_f[N];
ll qsm(int a,int b){
    ll ans=1,tmp=a;
    while( b ) {
        if( b&1 ) ans = ans * tmp%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
void ini(){
    int maxn = 1e5;
    fac[0]=1;
    _for(i,1,maxn) fac[i] =  (fac[i-1] * i)%mod;
    ni_f[maxn] = qsm(fac[maxn],mod-2);
    _rep(i,maxn-1,0) ni_f[i] = ni_f[i+1] * (i+1)%mod;
}
ll C(int n,int m){
    if( m==n || m==0 ) return 1;
    if( n < m ) return 0;
    return fac[n] * ni_f[n-m]%mod * ni_f[m]%mod;
}
int vis[N];
int dfs(int x ,int fa){
    vis[x]=1;
    int siz = 1;
    for(int y:G[x]){
        if( y==fa || vis[y]) continue;
        siz += dfs(y,x);
    }
    return siz;
}
vector<int> V;
Poly cal(int l,int r){
    if( l==r ){
        Poly ans(V[l]+1,0);
        _for(i,0,V[l]-1){
            ans[i] = C(V[l],i);
        }
        return ans;
    }
    int mid = (l+r)>>1;
    return mul(cal(l,mid) , cal(mid+1,r));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    IOS;
    ini();
    cin>>n;
    _for(i,1,n){
        cin>>a[i];
        G[i].push_back(a[i]);
        G[a[i]].push_back(i);
    }
    _for(i,1,n){
        if( !vis[i] ){
            int siz = dfs(i,0);
            V.push_back(siz);
        }
    }
    Poly F = cal(0,V.size()-1);
    int ans = 0;
    for(int i=0 ;i<F.size() ;i++){
        int flag = i&1?-1:1;
        ans = (ans + mod + flag * F[i] * fac[n-i]%mod)%mod;
    }
    cout<<ans<<endl;
    AC; 
}

Copyright © 2010-2022 kler.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号