目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://atcoder.jp/contests/abc247/tasks/abc247_f

---

二、解题报告

1、思路分析

P, Q 两个排列其实就是一个置换，由该置换我们可以得到一个置换环，环上一条边就代表原数组中的一对 <P[i], Q[i]>

我们要选出一些 i 使得 Pi, Qi 并集是 1~n 对应到图上就是每个置换环选出一些边覆盖所有点

即环上相邻边至少有一个必须选

那这就是经典的打家劫舍问题

我们需要预处理出一个数组dp，dp[i] 代表从长度为i 的环中，选出若干条边使得所有点都被覆盖的方案数

答案就是 dp[L[i]] 累乘，L[i] 是第i个置换环的长度

dp数组的计算其实是经典问题，假如不是环而是一条链的话，我们按照dp[i] = dp[i - 1] + dp[i - 2] 即可处理，但现在是环，所以需要分第一个边 选 / 不选分别dp再累加结果

Bonus：dp[] 构成了卢卡斯数列，它的递推和斐波那契一样，只不过L[1] = 1, L[2] = 3，所以可以一次dp预处理卢卡斯数列来替代dp[]

2、复杂度

时间复杂度： O(nα(n))空间复杂度：O(n)

3、代码详解

 ​

#include <bits/stdc++.h>
namespace ranges = std::ranges;
namespace views = std::views;
using i64 = long long;

constexpr int M = 998244353;
int add(int x, int y) {
    x += y - M;
    x += (x >> 31) & M;
    return x;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<int> P(N), Q(N), f(N), siz(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i];
        --P[i];
        f[i] = i;
        siz[i] = 1;
    }
    auto find = [&](int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    };
    auto merge = [&](int x, int y) {
        x = find(x); y = find(y);
        if (x == y) {
            return;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        siz[x] += siz[y];
        f[y] = x;
    };
    for (int i = 0; i < N; ++i) {
        std::cin >> Q[i];
        --Q[i];
        merge(P[i], Q[i]);
    }
    std::vector<int> dp(N + 1);
    dp[1] = 1;
    int f0 = 0, f1 = 1;
    for (int i = 2; i <= N; ++i) {
        std::tie(f0, f1) = std::pair(f1, add(f0, f1));
        dp[i] = add(f0, f1);
    }
    f0 = 1, f1 = 0;
    for (int i = 2; i <= N; ++i) {
        std::tie(f0, f1) = std::pair(f1, add(f0, f1));
        dp[i] = add(dp[i], f1);
    }
    int ans = 1;
    for (int i = 0; i < N; ++i) {
        if (find(i) == i) {
            ans = 1LL * ans * dp[siz[i]] % M;
        }
    }
    std::cout << ans << '\n';

    return 0;
}