「NOIP2021模拟赛8.19 C」玩家(gamer)

给定一个序列 ${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

#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;
}

评论

  1. OdtreePrincess
    Windows Chrome 80.0.3987.87
    4周前
    2021-8-26 18:49:00

    Σ(っ °Д °;) っ 没看懂 ⌇●﹏●⌇ orz (ó﹏ò。)

    • yzxoi 博主
      Windows Chrome 92.0.4515.159
      4周前
      2021-8-26 18:49:34

      ○| ̄|_

  2. OdtreePrince
    Windows Chrome 78.0.3904.108
    4周前
    2021-8-26 15:05:08

    Σ(っ °Д °;)っ 没看懂 ⌇●﹏●⌇ orz (ó﹏ò。)

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇