ABC247F Cards Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $1$$1$ 到 $n$$n$ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $1$$1$ 到 $n$$n$ 每个数至少一次。求有多少种取法，对 $998244353$$998244353$ 取模。

Solution

考虑卡片之间的联系，显然若一个数在同一张卡牌的正反面那么这张卡牌必须选择，否则无法凑齐一个排列，反之这个数一定会在两张卡牌中出现，且这两张卡牌一定至少有一张被选择，否则依然无法凑齐一个排列，这个很好理解。

于是我们考虑一些对于这种题的一般的套路，可以尝试建图，对于本题不难想到，我们将一张卡牌作为一个点，将这个点向卡牌上存在的数的另一次出现所在的卡牌连一条边。抽象地说，对于一个数所在的两张（或一张）卡牌位置 $po{s}_{i,0}$$pos_{i, 0}$ 和 $po{s}_{i,1}$$pos_{i, 1}$，其中一定有一个刚好为 $i$$i$，我们就是要从 $i$$i$ 向不等于 $i$$i$ 的那个 $po{s}_i$$pos_i$ 连一条边，这里便不难想到从 $i$$i$ 向 $po{s}_{i,0}\oplus po{s}_{i,1}\oplus i$$pos_{i, 0} \oplus pos_{i, 1} \oplus i$ 连边即可。

不难想到这样会形成多个环，每一个环代表着其中几张卡牌，同时这些卡牌上的数在环内一定每个数都出现了两遍，如排列 $\{1,2,3\}$$\{ 1, 2, 3 \}$ 和排列 $\{2,1,3\}$$\{ 2, 1, 3 \}$，显然 $i=1$$i = 1$ 时向数字 $1$$1$ 所在的另一张卡牌 $2$$2$ 和数字 $2$$2$ 所在的另一张卡牌 $2$$2$ 连边（不拿发现很有可能存在重边与自环，所以需要注意判重并忽略），对于 $i=2$$i = 2$ 同理，最终一定会形成 $1\to 2\to 1$$1 \rightarrow 2 \rightarrow 1$ 和 $3\to 3$$3 \rightarrow 3$ 两个环，第一个环可以求出带有 $1,2$$1, 2$ 数字的卡牌的让 $1,2$$1, 2$ 都至少存在一次的卡牌选择方案数，第二个环则为 $3$$3$ 的方案数，将两者乘起来即为最终答案。并且环上每个边相连的两个点，或者说两张卡牌，至少要被选择一张，因为一条边连结的两个卡牌一定存在着相同的数，为了保证构成排列至少需要选择一个。

同时发现不同环的方案数，只跟环的长度有关，于是我们考虑令 $dp(i)$$dp(i)$ 表示 $i$$i$ 个数构成的环，则有边界 $dp(1)=1$$dp(1) = 1$ 和 $dp(2)=3$$dp(2) = 3$，和转移 $dp(i)=dp(i-1)+dp(i-2)$$dp(i) = dp(i - 1) + dp(i - 2)$，大概就是我们考虑向原环中插入第 $i$$i$ 个数，如果选择第 $i$$i$ 个数，那么任意的前 $i-1$$i - 1$ 个数的合法方案都可以接上新的这个数，反之如果不选第 $i$$i$ 个，那么第 $i$$i$ 个的两侧都应该是选择的，这个时候我们直观地可以想到，固定其左右的两个然后由 $dp(i-3)$$dp(i - 3)$ 转移而来，但是这个是有遗漏的。观察发现对于 $i$$i$ 不选择的，是存在类似 $\cdots \to 0\to 1\to i(0)\to 1\to 0\to \cdots$$\cdots \rightarrow 0 \rightarrow 1 \rightarrow i(0) \rightarrow 1 \rightarrow 0 \rightarrow \cdots$，也就是在固定三个之后左右各自接一个不选的，这个东西显然是不在 $dp(i-3)$$dp(i - 3)$ 里的，因为两个都不选接在一起形成环是不合法的，考虑如何正确地转移：我们可以考虑在 $dp(i-2)$$dp(i - 2)$ 的方案中找到任意一个选择的点，然后在其旁边接上 $i$$i$ 和另一个固定的选择的点，这样也是合法的且不重不漏，最终就是 $dp(i)=dp(i-1)+dp(i-2)$$dp(i) = dp(i - 1) + dp(i - 2)$。

于是考虑并查集维护好每个环的大小，$\prod dp(si{z}_i)$$\prod dp(siz_i)$ 即为最终的答案。

Code

xxxxxxxxxx
78
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD 998244353
24

25
template< typename T = int >
26
inline T read(void);
27

28
int N;
29
int P[210000], Q[210000];
30
int cnt[210000];
31
int pos[210000][2];
32
int f[210000];
33
bool vis[210000];
34
int ans(1);
35

36
class UnionFind{
37
private:
38
public:
39
    int fa[210000];
40
    int siz[210000];
41
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i, siz[i] = 1;}
42
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
43
    void Union(int origin, int son){
44
        if(Find(origin) == Find(son))return;
45
        siz[Find(origin)] += siz[Find(son)], fa[Find(son)] = Find(origin);
46
    }
47
}uf;
48

49
int main(){
50
    N = read();
51
    f[1] = 1, f[2] = 3;
52
    for(int i = 3; i <= N; ++i)f[i] = (ll)(f[i - 1] + f[i - 2]) % MOD;
53
    for(int i = 1; i <= N; ++i)P[i] = read(), pos[P[i]][cnt[P[i]]++] = i;
54
    for(int i = 1; i <= N; ++i)Q[i] = read(), pos[Q[i]][cnt[Q[i]]++] = i;
55
    for(int i = 1; i <= N; ++i)
56
        uf.Union(i, pos[P[i]][0] ^ pos[P[i]][1] ^ i),
57
        uf.Union(i, pos[Q[i]][0] ^ pos[Q[i]][1] ^ i);
58
    for(int i = 1; i <= N; ++i)if(uf.Find(i) == i)ans = (ll)ans * f[uf.siz[uf.Find(i)]] % MOD;
59
    printf("%d\n", ans);
60
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
61
    return 0;
62
}
63

64
template < typename T >
65
inline T read(void){
66
    T ret(0);
67
    short flag(1);
68
    char c = getchar();
69
    while(c != '-' && !isdigit(c))c = getchar();
70
    if(c == '-')flag = -1, c = getchar();
71
    while(isdigit(c)){
72
        ret *= 10;
73
        ret += int(c - '0');
74
        c = getchar();
75
    }
76
    ret *= flag;
77
    return ret;
78
}

UPD

update-2022_10_25 初稿