「NOIP2021模拟赛8.19 C」玩家（gamer）

(Updated: )
oi
,

给定一个序列 ${a_i}$，统计有多少个排列 $p_1,\dots,p_n$ 对于任意 $i$ 满足 $p_i=a_i$ 或 $p_{p_i}=a_i$。

$1\leq n\leq 10^5,1\leq a_i\leq n$

$\texttt{2s/512MB}$

Sol

首先考虑一个满足条件的排列 $p$，一定会构成若干个环，使得每个点必然走一步/两步就能走到 $a_i$。每个点 $i$ 向 $p_i$ 或 $p_{p_i}$ 连边，可以发现如若合法，则构成的图一定是个基环内向树森林。考虑如何生成这样符合题意的图。

先反向连边，尝试构成一个基环外向树森林，显然每个点出度至多为 $2$。显然一定是若干个环以及若干条挂在环上的链。

那么先考虑如何合并环上的链，显然要么是紧跟在链与环间的端点后的，要么是与端点相隔一个点，然后与环上的点交织分布。如若交织过程中出现另一条链或者往外挂的链有分叉，显然是不可能合并起来的。

然后考虑计算环之间的答案，可以直接 DP，考虑对于每个大小的环分别考虑，如果这个环是奇环（且长度大于 $1$），显然有两种独立方案（这个可以自己画个图，额外的一个方案是全部都遵循 $p_{p_i}=a_i$，当环大小为偶数时会重叠），如果这个环是偶环，显然仅有一种独立方案。还有可能是两个环合并，那么显然得两个长度相同的环合并，显然直接乘上节点接在另一个环上哪个点之后即可，然后可以直接转移。

由于每个节点仅会被访问一次，且 DP 转移是线性的，所以时间复杂度 $\mathcal O(N)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,p=998244353;
int n,a[N],Ans=1,F[N],stk[N],top,len[N],deg[N],ci[N],fir[N],nxt[N],son[N],tot;
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
bool vis[N];
#define NA() (puts("0"),exit(0),0)
I int Dfs(CI x){return deg[x]>1&&NA(),(!fir[x]?0:Dfs(son[fir[x]]))+(vis[x]=1);}
I void Sol(CI x){
    RI lst,t=x,fi=0,i,j;W(!vis[t]) vis[t]=1,t=a[t];stk[top=1]=t;W((t=a[t])^stk[1]) stk[++top]=t;
    for(i=1;i<=top;i++) if(deg[stk[i]]>1) break ;if(i>top) return ++ci[top],void();
    for(lst=0,i=1;i<=top;i++) deg[stk[i]]>1&&(!fi&&(fi=i),len[i]=i-lst,lst=i);len[fi]+=top-lst;
    for(stk[0]=stk[top],i=1;i<=top;i++) if(deg[stk[i]]>1){
        for(j=fir[stk[i]];j;j=nxt[j]) son[j]^stk[i-1]&&(t=Dfs(son[j]));t>len[i]&&NA(),Ans=1LL*Ans*((t<len[i])+(t<=len[i]))%p;
    }return ;
}
int main(){
    RI i,j;for(read(n),i=1;i<=n;i++) read(a[i]),Add(a[i],i),(++deg[a[i]])>2&&NA();for(i=1;i<=n;i++) !vis[i]&&(Sol(i),0);
    for(F[0]=i=1;i<=n;Ans=1LL*Ans*F[ci[i++]]%p) for(j=1;j<=ci[i];j++) F[j]=(1LL*(1+(i&1&&i>1))*F[j-1]%p+1LL*i*(j-1)%p*F[j-2]%p)%p; 
    return writeln(Ans),0;
}