思路

对于包含数 \(x\) 的卡牌，两张之中必定要选择一张，由此想到 2-SAT 的思想。

我们将所有带有 \(x\) 的卡牌两两连边，每一条边连接的点都表示两点必须选择一个。

不难发现，我们这样会得出若干个环。（因为对于每一张卡牌的出边为 \(2\)，一定会形成环）

在每一个环中的选择情况，不会影响答案，所以考虑分析每一个环所能做的贡献，然后用分布乘法原理得出答案。

定义 \(dp_i\) 表示一个大小为 \(i\) 的环的贡献。

不难得出 \(dp_1 = 1,dp_2 = 3\)。对于 \(i \geq 3\) 的时候，需要分类讨论一下：

1. 如果 \(1\) 不选，贡献等同于一个大小为 \(i - 2\) 的环，贡献为 \(dp_{i - 2}\)。
2. 如果 \(1\) 选，贡献等同于一个大小为 \(i - 1\) 的环，贡献为 \(dp_{i - 1}\)。

所以，对于一个大小为 \(i\) 的环，贡献为 \(dp_{i - 1} + dp_{i - 2}\)。（正好是一个斐波那契数列）

因此，答案是（其中 \(sz_i\) 表示第 \(i\) 个环的大小）：

求环的大小直接用并查集即可。

Code

#include <bits/stdc++.h>  
#define int long long  
#define re register  
  
using namespace std;  
  
const int N = 2e5 + 10,mod = 998244353;  
int n,ans = 1;  
int f[N],dp[N],sz[N],id[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 1) + (r << 3) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int find(int x){  
    if (f[x] != x) return f[x] = find(f[x]);  
    return f[x];  
}  
  
inline void merge(int a,int b){  
    int x = find(a);  
    int y = find(b);  
    if (x != y){  
        f[x] = y;  
        sz[y] += sz[x];  
    }  
}  
  
signed main(){  
    n = read();  
    dp[1] = 1;  
    dp[2] = 3;  
    for (re int i = 1;i <= n;i++){  
        f[i] = i;  
        sz[i] = 1;  
        if (i >= 3) dp[i] = (dp[i - 1] + dp[i - 2]) % mod;  
    }  
    for (re int i = 1;i <= n;i++){  
        int x;  
        x = read();  
        id[x] = i;  
    }  
    for (re int i = 1;i <= n;i++){  
        int x;  
        x = read();  
        merge(i,id[x]);  
    }  
    for (re int i = 1;i <= n;i++){  
        if (f[i] == i) ans = ans * dp[sz[i]] % mod;  
    }  
    printf("%lld",ans);  
    return 0;  
}