当前位置：首页 > news >正文

21年icpc上海区域赛B题Strange Permutations (容斥+生成函数)

news 来源：原创 2024/5/10 2:38:11

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

$\quad$ 直接看这个式子有点晕，看到排列可以从图意义入手。
我们设P，Q的图意义为： $P_{Q_{i}}->Q_{i+1}$ ，当然反过来也一样的（这个意义想了几天，被 $i->P_{i+1}$ 的固有套路给框柱了，意义是可以自定义的）。如果考虑i从1到n的话，连出来肯定是若干环，这个和 $i->P_{i}$ 的建图意义是一样的。
$\quad$ 乱证一下：因为 $P_{Q_i}$ 是个排列， $Q_{i+1}$ 也是个排列（先假设Q{n+1}有意义），把两个排列按照 $Q_{i+1}$ 大小排序，就转化成了 $i->P_i$ 。
$\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}$
P:3 4 1 2
Q:1 4 3 2
$P_{Q_i}$ :3 2 1 4
$Q_{i+1}$ : 4 3 2 ？
根据上面的建图意义，这是合法的。
来组不合法的。
P:3 4 1 2
Q:1 3 4 2
$P_{Q_i}$ :3 2 1 4
$Q_{i+1}$ :3 4 2 ？
3指向3不合法了，发现用 $i->P_i$ 与这个建图意义的禁边意义是相同的！于是就可以转成n条禁边(i,Pi)。而n条禁边组成了若干环，我们要选的是哈密顿回路，所以不能有环。
$\quad$ 考虑容斥， $f (i)$ 表示钦定选i条禁边的哈密顿路径数，因为不能有环，所以对于禁边组成的若干环，每个环上的边都不能全取，则 $ans=\sum_{i=0}^{n-1}(-1)^i*f(i)$ (这是二项式反演，但不是没有组合数的容斥系数！容斥系数在后面的多项式计算里体现出来了！所以最外层不用带组合数！！！)。
设每个环多项式为 $\sum_{i=0}^{siz-1}C(siz,i)x^i$ ，其中siz为环大小。
$=\prod g_j, f(i)=[x^i]F$ ,即第i项的系数,F的计算用启发式合并算一下就可以了。
时间复杂度 $O(nlog^2n)$ 。
这题难点还是在求解问题的转化上。搞清楚后，很容易。
（因为这题结合别的大佬们的题解理解了好久，把一些自己想错的问题都写了，所以比较长，还有一些证明和理解也是自己瞎想的，如有不对的话，还请读者留言区指正，感谢）

#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; 
}