AtCoder Beginner Contest 247 F Cards

F - Cards

思路

把每一张牌想象成一条边，牌正面跟反面想象成点。那么这个问题就变成了，从大小为n的边集选出来一些子集合，是的这个子集完全覆盖住所有的点，问这些子集有多少个？

观察到

• P，Q是一个1～n的排列，所以每个1～n中的每个点总共出现两次，也就是说，每个点都有两条边与其相连
• 如果选上所有的边，那么1～n构成的图肯定是若干个环，且环上任意一条边只属于一个环，这个第一点已经证明。
• 所以我们可以单独考虑每个环有多少种方案，再利用乘法原理，把每个环的方案数量相乘即可得到答案。

现在考虑一个包含m个点的环，有多少种选边方案，使得可以完全覆盖这m个点。

考虑动态规划 $f[i][0/1][0/1](f[i][j][k])$表示总共有i个点 $j=0/1$表示第一条边没选/选了，$k=0/1$表示最后一条边选了/没选的方案数量。这里最后一条边指的是$(1,i)$

• 边界$f[1][0][0]=0,f[1][1][1]=1$,只有一个点时，第一条边和最后一条边都是$(1,1)$，只有这两条边都被选上，才有一种方案
• $f[i][j][0]=f[i?1][j][1]$最后一条边不选时，倒数第二条边必须要选上，不然i号点就成为了孤立点。
• $f[i][j][1]=f[i?1][j][0]+f[i?1][j][1]$，最后一条边选上时，倒数第二条边可以选，也可以不选。

所以，i个点构成的环的总方案数量为$f[i][0][1]+f[i][1][0]+f[i][1][1]$, 第一条和最后一条都不选时不合法，所以不能计入答案。

记答案为$g[i]$, 再代入上面的状态转移方程，发现
$g[i]=f[i][0][1]+f[i][1][0]+f[i][1][1]$
$=f[i?1][1][1]+f[i?1][0/1][0]+f[i?1][0/1][1]$
$=(f[i?1][1][1]+f[i?1][1][0]+f[i?1][0][1])+(f[i?1][0][0]+f[i?1][1][1])$
$=g[i?1]+(f[i?1][0][0]+f[i?1][1][1])$
$=g[i?1]+(f[i?2][0][1]+f[i?2][1][0]+f[i?2][1][1])$
$=g[i?1]+g[i?2]$

所以我们得到一个更简易的状态转移方程（不化简也没关系，反之不影响答案)
$g[i]=g[i?1]+g[i?2]$

有了这个，我们只需要统计每个环有多少个点，然后利用预处理出来的g[i]算出答案

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef long long LL;typedef pair<int,int> PII;int n, m;
bool multi = false;
int a[N], b[N];
int f[N];struct Dsu
{
    vector<int> p, sz;int n;void init(int _n) {
    n = _n;p.resize(n + 1);sz.resize(n + 1, 0);for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;}int find(int x) {
    return p[x] != x ? p[x] = find(p[x]) : p[x];}void merge(int a, int b) {
    int x = find(a), y = find(b);p[x] = y;if(x != y) sz[y] += sz[x];}
}dsu;void solve() {
    cin >> n;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < n; i++) cin >> b[i];dsu.init(n);for(int i = 0; i < n; i++) dsu.merge(a[i], b[i]);//f[i]总共i个点f[1] = 1, f[2] = 3;for(int i = 3; i <= n; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;}int res = 1;for(int i = 1; i <= n; i++) {
    if(dsu.find(i) == i) {
    res = (LL)res * (f[dsu.sz[i]]) % mod;}}cout << res << endl;}int main()
{
    
#ifdef ONLINE_JUDGE
#else freopen("F.txt", "r", stdin);
#endifint T = 1;if(multi) cin >> T;while(T--) solve();return 0;
}