「NOIP2021模拟赛8.19 C」玩家（gamer）
给定一个序列 {a_i}，统计有多少个排列 p_1,dots,p_n 对于任意 i 满足 p_i=a_i 或 p_{p_i}=a_i。
1leq nleq 10^5,1leq a_ileq 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
代码语言：javascript复制#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 '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;
}
