题解：P11281 「GFOI Round 2」Aob & Blice

Solution

形式化题意：

给定序列 a，若 a_i=0 则代表未知。

问有多少种排列 p 满足 \forall i,p_{p_i}=i。

为什么可以转化为以上题意呢？

因为 x<y 且 p_x>p_y，若要满足题意必须对于任意 x,y 满足 x=p_y 且 y=p_x。

而满足上述要求的无非两种情况：

• p_i=i
• p_i=j$ 且 $p_j=i

形式化一点说就是 p_{p_i}=i。

转换完题目后再看本题，记 cnt=\sum[a_i=0]，我们先从确定的位置入手：

• 若 a_{a_i}=i，满足要求。

• 否则若 a_{a_i}=0，那么为了满足题意，a_{a_i} 就一定要赋值为 i，cnt\leftarrow cnt-1。

• 否则一定不满足题意，输出 0 即可。

接下来的问题就变为了，对于一个长为 cnt 的排列 p，有多少种赋值方案能够满足 \forall i,p_{p_i}=i。

至于这些数是否能与原 a 序列构成排列已不重要了，毕竟我们只在乎数与数之间的关系。

明显的计数 dp，令 dp_{i,0/1} 表示前 i 个位置的总方案数。其中 op=0 表示此时 p_i=i，op=1 代表 p_i<i 且 p_{p_i}=i。

最终答案：dp_{cnt,0}+dp_{cnt,1}。

有个坑点，注意特殊性质 A 中 cnt=0，此时需要特判答案为 1（假设有解）或是将 dp_{0,0}\leftarrow 1 即可解决。

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
const int M=998244353;
int n,a[N],ans=1,cnt,dp[N][2];
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!a[i]) cnt++;
    }
    for(int i=1;i<=n;i++){
        if(!a[i]) continue;
        if(i!=a[a[i]]){
            if(a[a[i]]){
                cout<<0;
                return 0;
            }   
            cnt--;
        }
    }
    dp[0][0]=dp[1][0]=dp[2][0]=dp[2][1]=1;
    for(int i=3;i<=cnt;i++){
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%M;
        dp[i][1]=(i-1)*dp[i-1][0]%M;
    }
    cout<<(dp[cnt][0]+dp[cnt][1])%M;
    return 0;
}