F - Cards
题意：
给你n个卡片，每个卡片正背面各有一个数字，大小为1到n，问你有多少种选法让选出的情况使1
到n都出现过。
题解：
看到这种情况肯定想到dp。但是怎么dp呢。考虑在卡片上两个数字连一条边，这样我们能得到一个环。那么对于每种环的大小dp出对应的种数，再把每个环乘起来就行了。那么细节就回到了环上dp。
对于这道题：我们连接环，大概是1-2，2-3，这样，那么每两条边不能同时不选，其他情况都满足。
s对应0，1，表示第一条边选不选，满足环上要求。
找环当然是并查集最好写了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
typedef long long ll;
const ll mod=998244353;
const int N=201000;
int p[N],q[N],f[N],n,sz[N];
ll dp[N][2][2],ans[N];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);
}
int main() {scanf("%d",&n);rep(i,1,n+1) scanf("%d",p+i);rep(i,1,n+1) scanf("%d",q+i),f[i]=i;rep(i,1,n+1) {f[find(p[i])]=find(q[i]);}rep(i,1,n+1) sz[find(p[i])]++;dp[1][0][0]=1;dp[1][1][1]=1;ans[1]=1;rep(i,2,n+1) {rep(s,0,2) {dp[i][s][0]=dp[i-1][s][1];dp[i][s][1]=(dp[i-1][s][1]+dp[i-1][s][0])%mod;}ans[i]=(dp[i][1][1]+dp[i][0][1]+dp[i][1][0])%mod;//printf("%d %lld\n",i,ans[i]);}ll ret=1;rep(i,1,n+1) if (f[i]==i) ret=ret*ans[sz[i]]%mod;printf("%lld\n",ret);
}