Problem Summary#

You have $N$ cards. Each card has two sides — the front shows a number $P_i$ and the back shows $Q_i$. Both sequences $P$ and $Q$ are permutations of $(1, 2, \dots, N)$. Count the number of subsets of cards such that every number from $1$ to $N$ appears on at least one chosen card. Output the answer modulo $998244353$. $(1 \le N \le 2 \times 10^5)$

Approach#

Build a graph by connecting the two numbers on each card. Since $P$ and $Q$ are permutations, every value appears exactly twice, so every vertex has degree $2$ and the resulting graph is a disjoint union of cycles.

Consider a simpler sub-problem first: on a chain of $m$ numbers $1, 2, \dots, m$, count the ways to pick a subset such that for every pair of adjacent numbers at least one is chosen. Splitting by whether $m$ is picked, let $f(m)$ denote the answer. We have $f(1) = 2$, $f(2) = 3$, and $f(m) = f(m-1) + f(m-2)$ — Fibonacci-like.

Now the real sub-problem: on a cycle of $m$ numbers, count the subsets where for every vertex at least one of its two incident edges is chosen. Let $g(m)$ denote the answer. Casework on whether the edge $(1, m)$ is picked gives $g(1) = 1$, $g(2) = 3$, and $g(m) = f(m-1) + f(m-3)$. A quick check reveals $g(m) = L_m$, the $m$-th Lucas number.

Multiply $g(\text{cycle length})$ across every cycle in the graph to get the final answer.

Code#

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
}