P11563 Sol

· · 题解

我擦，企鹅罐！生存战略！

挺好的性质题。写详细亿点。

排列可以看成有向环集合来计数。设在 p 上对于每个 i，在图上连接 i\leftrightarrow p_i 得到的无向图为 G_1，在 a 上对于每个 i 连接 i\to a_i 得到的有向图为 G_2。那么 a 合法仅当 G_1 的每条边的其中一个方向都在 G_2 中出现。G_1 已知了，我们需要知道合法的 G_2 数，考虑刻画。

首先由于 a 是排列，G_2 只包含有向环，那么 G_1 出现一个度数 \ge 3 的点就包没合法 G_2 的。考虑到 G_1 出来会是个基环森林，都不能有森林了，看起来 G_1 也必须是一堆环构成的啊？

（观察样例）发现有个奇怪情况：G_1 里有二元环。你会发现这里我们应该要将这个二元环当作一条无向边来看待，因为 G_2 只需要有一条有向边就可以同时消灭二元环里的两条边。

于是把二元环换成无向边后 G_1 里出现了链！现在看看怎么个事。

别急，还有高手！如果 G_2 里又连出了二元环，这时这个环的两种定向方式在 G_2 里看起来是一样的！算重到起飞！

这种情况要求 G_1 里存在一个孤单的二元环被变成了一条无向边，然后我们在后期连接的时候直接将它的两端连了起来。设 G_1 中这样单独的一条无向边作一条链的条数为 y。

没事还可以容斥，我们钦定其中 i 条边在 G_2 里被当成二元环的另一个方向算重的方案数为 f_i。有 f_i=\binom{y}{i}2^{x-i}(x-i)!。最后 ans=2^k\sum\limits_{i=0}^y(-1)^if_i。

实现就是看看 G_1 里上面几种东西都有几种，算就完了。小心漏了什么阴间情况。

const ll J=1e18,N=1e6+7,P=998244353;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll fac[N],fnv[N];
struct init { init() {
    fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
    fnv[N-1]=qp(fac[N-1]); for (ll i=N-1;i;i--) fnv[i-1]=fnv[i]*i%P;
} } A;
ll C(ll x,ll y) { return x<0||y<0||x<y?0:fac[x]*fnv[y]%P*fnv[x-y]%P; }
ll n,a[N],ans,vis[N];
ll c3,c21,c22;
vector<ll> e[N];
void no() { cout<<"0",exit(0); }
void get(ll p) {
    if (e[p].size()>1) no();
    vis[p]=1;
    if (e[p].size()==1&&!vis[e[p][0]]) get(e[p][0]);
}
void mian() {
    scanf("%lld",&n);
    for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),e[a[i]].pb(i);
    for (ll i=1;i<=n;i++) if (!vis[i]) {
        if (a[i]==i) {
            if (e[i].size()>1) no();
            vis[i]=1;
        }
        else if (a[a[i]]==i) {
            ll x=i,y=a[i],flg=0;
            vis[x]=vis[y]=1;
            if (e[x].size()>2||e[y].size()>2) no();
            if (e[x].size()==2) flg=1,get(e[x][0]^e[x][1]^y);
            if (e[y].size()==2) flg=1,get(e[y][0]^e[y][1]^x);
            flg?c22++:c21++;
        }
    }
    for (ll i=1;i<=n;i++) if (!vis[i]) {
        if (!e[i].size()) no();
        c3++,get(i);
    }
    ll ans=0;
    for (ll i=0;i<=c21;i++) (ans+=(i&1?P-1:1)*C(c21,i)%P*qp(2,c21+c22-i)%P*fac[c21+c22-i])%=P;
    cout<<ans*qp(2,c3)%P;
}