P11281 「GFOI Round 2」Aob & Blice

让我们思考一下“无限轮”。

不难发现，根据 Aob 的行动方式，经过足够次随机后，最终集合 S_A=\set{(i,j),(p_i,p_j)|1\le i<j\le n,p_i>p_j}，即排列 \set{p_n} 中所有逆序对及其对应下标。

因此只需要考虑 S_B 即可。

对于一组满足 1\le i<j\le n,p_i>p_j 的 (i,j)，显然 (j,i)\neq(i,j)。为了使 S_B=S_A，S_B 中应当存在 (p_j,p_i)=(i,j)；同时，S_A 中也应当有 (p_{p_i},p_{p_j})=(p_j,p_i)。将两式合并，得到 p_{p_i}=i。

这样我们已经完成了性质 A，只需要统计对于每个 p_i 是否满足 p_{p_i}=i 即可，若不满足直接输出 0。接下来考虑排列 \set{p_n} 有缺失的情况。

我们先将能填充的缺失部分填好。对于 p_i\neq0 的项，若 p_{p_i}=0，那我们可以直接将 p_{p_i} 填上 i。

当所有能填的空填完后，问题就转化为了性质 B。记排列 \set{p_n} 中有 cnt 项为 0，我们需要求出对这些空格填空的总方案数。对于第 i 个空，我们要么填入 i，要么填入 k 同时在第 k 个空填入 i。

这个是问题相当于求数列 A000085，记 dp(i) 为有 i 个空时的总方案数，则 dp(i)=dp(i-1)+dp(i-2)\times(i-1)，边界为 dp(0)=dp(1)=1，答案为 dp(cnt)。场上查到 oeis 之后把递推式打成了 dp[i]=dp[i-1]-(cnt-1)*dp[i-2] 怒挂 70 分，唐！

至此，此题得解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+10,P=998244353;

int n,p[MAXN],dp[MAXN];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++)
    {
        if(p[i]&&!p[p[i]])p[p[i]]=i;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(p[i]==0)cnt++;
        else if(p[p[i]]==i)continue;
        else
        {
            cout<<0;
            return 0;
        }
    }
    dp[0]=dp[1]=1;
    for(int i=2;i<=cnt;i++)dp[i]=(dp[i-1]+dp[i-2]*(i-1))%P;
    cout<<dp[cnt];
    return 0;
}