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

题面比较抽象，这里写一个较为好理解的题面。

对于一个排列 p，以下面的方式定义矩阵 s 与 t：

对于任意 1\le x<y\le n 且 p_x>p_y，s_{x,y}=1，s_{p_x,p_y}=1；t_{y,x}=1，t_{p_y,p_x}=1。

没被赋 1 的位置为 0。

求使 s=t 的原排列个数。

根据定义知 s_{x,y}=t_{y,x}，联立 s_{y,x}=t_{y,x} 得 s_{x,y}=s_{y,x}，消去 t。

令 q 为 p 的逆排列，则如果 x<y，s_{x,y}=[p_x>p_y]\lor[q_x<q_y]（分别对应 s_{x,y}=1 和 s_{p_x,p_y}=1）；如果 x>y，s_{x,y}=[p_x<p_y]\lor[q_x>q_y]。

则 [p_x>p_y]\lor[q_x<q_y]=[p_x<p_y]\lor[q_x>q_y]。因为 [p_x>p_y] 与 [p_x<p_y] 有且仅有一个为 1（q 同理），所以两边等于 1。

若 [p_x>p_y]=1，则 [p_x<p_y]=0，[q_x>q_y]=1，[q_x<q_y]=0。[p_x>p_y]=0 同理。

换句话说，[p_x>p_y]=[q_x>q_y]。

又因为 p,q 均为排列，所以 p_x=q_x，即 p_{p_x}=x。

把排列视为置换，x 向 p_x 连边，得出来的图没有长度大于 2 的环。

先判掉 p_{p_x}\ne0 且 p_{p_x}\ne x 的情况。剩下有些数没被确定，可以在保证环长 \le2 的情况下随便填。

问题转化为，对于一个长度为 k 的排列，有多少种方案使得所有环长 \le2，即 B 性质。

我们从前往后考虑，设 f_i 为长度为 i 的方案数。新加一个数有两种情况：

1. 自己单独成环，f_i\leftarrow f_{i-1}。
2. 和之前的某个数成环，f_i\leftarrow f_{i-2}\cdot(i-1)。

初值：f_0=f_1=1。

int n,ans,a[N],b[N],f[N];
void QwQ() {
    n=rd(),f[0]=f[1]=1;
    for(int i=2;i<=n;i++) f[i]=vadd(f[i-1],vmul(i-1,f[i-2]));
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=n;i++) if(a[i]) {
        b[i]=b[a[i]]=1;
        if(a[a[i]]&&a[a[i]]!=i) return puts("0"),void();
    }
    wr(f[count(b+1,b+1+n,0)],"\n");
}