ABC247F Cards Solution
目录更好的阅读体验戳此进入
题面
给定 $ n $ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $ 1 $ 到 $ n $ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $ 1 $ 到 $ n $ 每个数至少一次。求有多少种取法，对 $ 998244353 $ 取模。
Solution
考虑卡片之间的联系，显然若一个数在同一张卡牌的正反面那么这张卡牌必须选择，否则无法凑齐一个排列，反之这个数一定会在两张卡牌中出现，且这两张卡牌一定至少有一张被选择，否则依然无法凑齐一个排列，这个很好理解。
于是我们考虑一些对于这种题的一般的套路，可以尝试建图，对于本题不难想到，我们将一张卡牌作为一个点，将这个点向卡牌上存在的数的另一次出现所在的卡牌连一条边。抽象地说，对于一个数所在的两张（或一张）卡牌位置 $ pos_{i, 0} $ 和 $ pos_{i, 1} $，其中一定有一个刚好为 $ i $，我们就是要从 $ i $ 向不等于 $ i $ 的那个 $ pos_i $ 连一条边，这里便不难想到从 $ i $ 向 $ pos_{i, 0} \oplus pos_{i, 1} \oplus i $ 连边即可。
不难想到这样会形成多个环，每一个环代表着其中几张卡牌，同时这些卡牌上的数在环内一定每个数都出现了两遍，如排列 $ { 1, 2, 3 } $ 和排列 $ { 2, 1, 3 } $，显然 $ i = 1 $ 时向数字 $ 1 $ 所在的另一张卡牌 $ 2 $ 和数字 $ 2 $ 所在的另一张卡牌 $ 2 $ 连边（不拿发现很有可能存在重边与自环，所以需要注意判重并忽略），对于 $ i = 2 $ 同理，最终一定会形成 $ 1 \rightarrow 2 \rightarrow 1 $ 和 $ 3 \rightarrow 3 $ 两个环，第一个环可以求出带有 $ 1, 2 $ 数字的卡牌的让 $ 1, 2 $ 都至少存在一次的卡牌选择方案数，第二个环则为 $ 3 $ 的方案数，将两者乘起来即为最终答案。并且环上每个边相连的两个点，或者说两张卡牌，至少要被选择一张，因为一条边连结的两个卡牌一定存在着相同的数，为了保证构成排列至少需要选择一个。
同时发现不同环的方案数，只跟环的长度有关，于是我们考虑令 $ dp(i) $ 表示 $ i $ 个数构成的环，则有边界 $ dp(1) = 1 $ 和 $ dp(2) = 3 $，和转移 $ dp(i) = dp(i - 1) + dp(i - 2) $，大概就是我们考虑向原环中插入第 $ i $ 个数，如果选择第 $ i $ 个数，那么任意的前 $ i - 1 $ 个数的合法方案都可以接上新的这个数，反之如果不选第 $ i $ 个，那么第 $ i $ 个的两侧都应该是选择的，这个时候我们直观地可以想到，固定其左右的两个然后由 $ dp(i - 3) $ 转移而来，但是这个是有遗漏的。观察发现对于 $ i $ 不选择的，是存在类似 $ \cdots \rightarrow 0 \rightarrow 1 \rightarrow i(0) \rightarrow 1 \rightarrow 0 \rightarrow \cdots $，也就是在固定三个之后左右各自接一个不选的，这个东西显然是不在 $ dp(i - 3) $ 里的，因为两个都不选接在一起形成环是不合法的，考虑如何正确地转移：我们可以考虑在 $ dp(i - 2) $ 的方案中找到任意一个选择的点，然后在其旁边接上 $ i $ 和另一个固定的选择的点，这样也是合法的且不重不漏，最终就是 $ dp(i) = dp(i - 1) + dp(i - 2) $。
于是考虑并查集维护好每个环的大小，$ \prod dp(siz_i) $ 即为最终的答案。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD 998244353
template< typename T = int >
inline T read(void);
int N;
int P[210000], Q[210000];
int cnt[210000];
int pos[210000][2];
int f[210000];
bool vis[210000];
int ans(1);
class UnionFind{
private:
public:
int fa[210000];
int siz[210000];
UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, siz[i] = 1;}
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
void Union(int origin, int son){
if(Find(origin) == Find(son))return;
siz[Find(origin)] += siz[Find(son)], fa[Find(son)] = Find(origin);
}
}uf;
int main(){
N = read();
f[1] = 1, f[2] = 3;
for(int i = 3; i <= N; ++i)f[i] = (ll)(f[i - 1] + f[i - 2]) % MOD;
for(int i = 1; i <= N; ++i)P[i] = read(), pos[P[i]][cnt[P[i]]++] = i;
for(int i = 1; i <= N; ++i)Q[i] = read(), pos[Q[i]][cnt[Q[i]]++] = i;
for(int i = 1; i <= N; ++i)
uf.Union(i, pos[P[i]][0] ^ pos[P[i]][1] ^ i),
uf.Union(i, pos[Q[i]][0] ^ pos[Q[i]][1] ^ i);
for(int i = 1; i <= N; ++i)if(uf.Find(i) == i)ans = (ll)ans * f[uf.siz[uf.Find(i)]] % MOD;
printf("%d\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_10_25 初稿
标签：int,题解,卡牌,210000,ABC247F,Cards,define,dp,rightarrow From： https://www.cnblogs.com/tsawke/p/16945511.html