题解：P11563 【MX-X7-T4】[LSOT-3] 命运

· · 题解

口胡一下。假了就删题解跑路。

把原题的序列看成给定每个点的父亲，于是得到基环树。

然后题目中排列的确定方式，看起来就像，要么继承基环树的原始边，要么给边反个向抄下来。

看眼样例，我草怎么假了。

我草怎么还有二元环，这么恐怖。不是很会，先放着等会来想。

如果是自环怎么办。分讨一下发现这个边好像动不了。

因为我们变形后的图要求是若干个环，因此如果自环下面有挂点那么就炸完了。

考虑三元环以及更多元的情况。

显然的这个时候依旧是边反向，于是这个环也是钉死的，所以环下面挂点一样是死路一条。

于是好像特例就只有二元环。

其他环如果合法，产生的贡献也只有顺时针一遍环以及逆时针一遍环。自环要扔掉。

考虑这个时候咋做，我们得到了一个基二元环树森林。

考察原始定义，我们需要保证对于每个原先存在的边，新图中存在其反向边或者原边。

所以二元环中的一个边可以直接被挪出来，于是变成多个树的问题。

然后容易发现如果树不是一条链的话加边是不会成环的。本质问题是环不会出现度数超过预期 2 的点，而你只能加边不能断边，所以拼树也无济于事。

那么我们有了许多链。

现在我们可以把这些链拼成若干个环。然后你发现这等价于排列数。

于是应该差不多是做完了。每个环还可以反个向啥的，反正就是个很普通的数数。

注意二元环独立成环的时候正反都一样，此时不应该乘这个 2，所以应该还得再上个容斥。

预处理信息可以用并查集。

#include<bits/stdc++.h>
#define N 1000000
#define mod 998244353
#define int long long
using namespace std;
int qpow(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
map<int,bool>mp[N+5];
int fa[N+5];
bool flg[N+5];
bool ban[N+5];
int siz[N+5];
int A[N+5],inv[N+5];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int C(int n,int m){
    return A[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    int n;
    cin>>n;
    A[0]=1;
    for(int i=1;i<=N;i++)
    A[i]=A[i-1]*i%mod;
    inv[N]=qpow(A[N]);
    for(int i=N;i;i--)
    inv[i-1]=inv[i]*i%mod;
    for(int i=1;i<=n;i++)
    fa[i]=i,siz[i]=1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==i){
            ban[i]=1;
            continue;
        }
        if(!mp[x][i]){
            if(find(x)==find(i))
            flg[find(x)]=1;
            else
            flg[find(i)]|=flg[find(x)],
            siz[find(i)]+=siz[find(x)],
            fa[find(x)]=find(i);
        }
        mp[x][i]=1;
        mp[i][x]=1;
    }
    int ret2=1;
    int sum1=0,sum2=0;
    for(int i=1;i<=n;i++){
        if(mp[i].size()>2){
            cout<<"0\n";
            return 0;
        }
        if(ban[i]&&siz[find(i)]!=1){
            cout<<"0\n";
            return 0;
        }
        if(ban[i])continue;
        if(i!=fa[i])continue;
        if(siz[i]==1)continue;
        if(flg[i]){
            ret2=ret2*2%mod;
            continue;
        }
        sum1++;
        if(siz[i]==2)sum2++;
    }
    int op=1;
    int ret=0;
    for(int i=0;i<=sum2;i++){
        int flc=C(sum2,i)*qpow(2,sum1-i)%mod*A[sum1-i]%mod;
        ret+=flc*op;
        ret%=mod;
        ret+=mod;
        ret%=mod;
        op=-op;
    }
    cout<<ret*ret2%mod;
    return 0;
}
//「呃，不是你想的那样啦。」

//「我明白，我全都明白，好吗？」
// 缇亚忒温柔地重复道。她绝对什么都不明白。