Cards (ABC 247 F) - ペンギンの巣

题目大意#

你有 $N$ 张卡片，每张卡有正反两面，正面有一个数字 $P_i$ ，反面有一个数字 $Q_i$ ，数列 $P$ 和 $Q$ 都是 $(1,2,\dots,N)$ 的全排列，问有多少种选择方法使得 $N$ 个数都至少一次出现在被选中的牌上，答案对 $998244353$ 取模。 $(1\le N\le2\times 10^5)$

思路#

首先，我们建一张图，把每张牌正反的两个数连起来，而由于 $P$ 和 $Q$ 是全排列，每个数都只会出现两次，每个点的度都是 $2$ ，所以我们建出来的图会由很多个环构成。然后我们先来考虑一个简单一点的问题： $1,2,\dots,m$ 这 $m$ 个数中相邻的两个数至少得选一个的方案数是多少。就是分类讨论 $m$ 是否选，这样的话，设答案为 $f(m)$ ，则满足 $f(1)=2,f(2)=3,\dots,f(m)=f(m-1)+f(m-2)$ 。然后现在我们要求的是 $1,2,\dots,m$ 这 $m$ 个数围成一个圈时连着一个点的两条边至少得选一条的方案数，设答案为 $g(m)$ ，分类讨论一下 $1$ 和 $m$ 是否相连，就能得到 $g(1)=1,g(2)=3,\dots,g(m)=f(m-1)+f(m-3)$ ，观察一下可以发现 $g(m)=L_m$ ， $L$ 为卢卡斯数列。这样，我们只要把每个环的答案乘起来就结束了。

代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
long long a[200005];
4
long long mod=998244353;
5
int p[200005];
6
int q[200005];
7
int fa[200005];
8
int siz[200005];
9
int vis[200005];
10
int findd(int x)
11
{
12
    return fa[x]==x?x:(fa[x]=findd(fa[x]));
13
}
14
int main()
15
{
16
    int n;
17
    scanf("%d",&n);
18
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
19
    for(int i=1;i<=n;i++)scanf("%d",&q[i]);
20
    for(int i=1;i<=n;i++){fa[i]=i;siz[i]=1;}
21
    for(int i=1;i<=n;i++)if(findd(p[i])!=findd(q[i]))
22
    {
23
        siz[findd(q[i])]+=siz[findd(p[i])];
24
        fa[findd(p[i])]=findd(q[i]);
25
    }
26
    a[0]=2;
27
    a[1]=1;
28
    for(int i=2;i<=n;i++)a[i]=(a[i-1]+a[i-2])%mod;
29
    long long ans=1;
30
    for(int i=1;i<=n;i++)if(!vis[findd(i)])
31
    {
32
        ans=ans*a[siz[findd(i)]]%mod;
33
        vis[findd(i)]=1;
34
    }
35
    printf("%lld\n",ans);
36
    return 0;
37
}