# 4月CF练题题解
1811D
1814C
1819B
1821D
1770D
题意：
Koxia 和 Mahiru 正在玩一个游戏。游戏使用 \(a,b,c\) 三个长度为 \(n\) 的数组，共进行 \(n\) 轮。
每一轮中，Koxia 先在 \(a_i,b_i,c_i\) 中选择一个数字，Mahiru 再从未选择的两个数字中选择一个。
如果 \(n\) 轮后 Mahiru 选择的数字刚好包含 \(1\) 至 \(n\) 中每个数字各一个（即为 \(1\) 至 \(n\) 的一个排列），则 Koxia 获胜。否则，Mahiru 获胜。
假设双方都采取最优策略，给定 \(a,b\) 数组，求使得 Koxia 必胜的 \(c\) 数组的个数。
题解：
因为两人都足够聪明，所以想赢就只有一种可能——先手可以限制后手怎么走
回到这个问题，如果后手方案确定，当且仅当剩下两个数是一样的，这样后手就会被先手牵着鼻子走
那么进行分类讨论可以确定必要条件：
- \(a_i=b_i\) 此时 \(c_i\) 有 \(n\) 种取法
- \(a_i\neq b_i\) 此时 \(c_i\) 有两种取法，分别对应 \(a_i,b_i\)
但这个条件不够充分。
对于这类或关系的处理，图论建模是一个很好的方法。
我们将一对\(a_i,b_i\)进行连边，问题化为每条边都必须指定端点的其中之一，不重不漏。考虑什么条件下是合法的。
下面我们证明有且仅有环是合法的，我们分连通块来讨论这个问题，显然不同连通块是 不会互相影响的。
先证充分性：按着环跑一圈一定是合法的
再证必要性：
- 假设它是一棵树，则 \(|E|<|V|\)，必定存在点连不到(树根)，答案变0
- 假设它连通，但 \(|E|>|V|\)，则必然会取到重复的，答案直接变0
统计\(|V|>1\)环的个数(并查集即可)，记为 \(c\)，\(|V|=1\) 环的个数记为\(s\)
\(ans=2^cn^s\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 205050
int f[N],num,a[N],b[N],n,m,ans=1,dfn[N],low[N],dcc,cnt[N],scc[N],tot=1,vis[N],siz[N],V[N];
int get(int x){
return x==f[x]?x:f[x]=get(f[x]);
}
void solve(){
for(int i=1;i<=n;i++){
if(i!=f[i]||V[i])continue;
if(siz[i]==cnt[i]&&vis[i]){
ans=1ll*ans*n%998244353;continue;
}
ans=1ll*ans*(siz[i]==cnt[i])*2%998244353;
}
}
void clear(){
for(int i=1;i<=n;i++)siz[i]=cnt[i]=V[i]=vis[i]=0;
dcc=num=0,tot=ans=1;
}
int main(){
int t;cin>>t;
while(t--){
clear();
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];f[i]=i;siz[i]=1;
}
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++){
int u=get(a[i]),v=get(b[i]);
if(u==v){
if(a[i]==b[i])vis[u]=1;
cnt[v]++;continue;
}
f[u]=v,cnt[v]+=cnt[u]+1,siz[v]+=siz[u],vis[v]|=vis[u];
}
solve();
cout<<ans<<"\n";
}
}