P6280 [USACO20OPEN]Exercise G题解

hhhyyyfff · 2020-04-04 15:11:05 · 题解

• 题意简述：
  已知 N,M\ (1 \le N \le 10^4,10^8 \le M \le 10^9+7,M\text{为质数})。
  有一个操作：给出两个排列 \{a_i\},\{b_i\}，得出一个排列 \{c_i\}，其中 c_i=a_{b_i}，最后 a \gets c。
  初始的排列 a 为 (1,2,3,\dots,N)，有一个排列 (p_1,p_2,p_3,\dots,p_N)，对 \{a_i\},\{p_i\} 反复进行操作，直到排列 a 又一次变成 (1,2,3,\dots,N)，记操作次数为 K。
  对于所有的排列 \{p_i\}，求有多少种 K 是可能的，答案对 M 取模。

• 前置知识：DP，筛法

• 算法分析 O(N^2 \times \text{小常数})：
  对于给定的排列 p，题目中的操作次数可以这样求：将排列 p 拆分成几个部分，每个部分 S 满足 \forall i \in S, p_i \in S，且不可再拆分。答案可表示为 |S_i| 的最小公倍数。
  例如 p=(2,5,4,3,1)，(2,5,1) 为一部分 (4,3) 为另一部分。
  因此，我们只需要枚举 |S_i| 即可，题目变成枚举 N 的拆分。对于合数 a=p_1^{c_1}p_2^{c_2} \dots p_n^{c_n}, 对最大公倍数（即答案）的贡献等价于 p_1^{c_1},p_2^{c_2},\dots,p_n^{c_n},1,1,\dots,1（a-\sum p_i^{c_i}的部分用 1 补全）。又因为，1 对答案实际没有贡献，所以只需对 1,2,\dots,N 分别用质数拆分。
  例如 N=6，分别对 1,2,3,4,5,6 用质数进行拆分。对 5 的拆分有 2+3；对 6 的拆分有 2+2+2 和 3+3。
  设 f_{i,j} 表示对 i 用质数拆分，最大的质数不超过 p_j，答案（K 的可能数）为 f_{i,j}。f_{i,j}有两个来源：f_{i,j-1} 即最大的质数小于 p_j 的方案；f_{i-kp_j,j-1} 即最大质数为 p_j，枚举这个质数在拆分中的数量 k。 f_{i,j}=f_{i,j-1}+\sum f_{i-kp_j,j-1}。
  这样能保证不漏（所有方案都能用质数拆分表示）不重（不同的质数拆分积不同，即 K 不同）。

• 代码：

#include <cstdio>

using namespace std;

int N, M, ans, cnt, f[10010][1300];
long long p[1300];
bool v[10010];

int main() {
    freopen("exercise.in", "r", stdin);
    freopen("exercise.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (int i = 2; i <= N; ++i)
        if (!v[i]) {
            p[++cnt] = i;
            for (int j = i; i * j <= N; ++j) v[i * j] = 1;
        }
    for (int i = 0; i <= cnt; ++i) f[0][i] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            f[i][j] = f[i][j - 1];
            for (long long k = p[j]; k <= i; k *= p[j])
                f[i][j] = (f[i][j] + f[i - k][j - 1] * k) % M;
        }
        ans = (ans + f[i][cnt]) % M;
    }
    printf("%d\n", (ans + 1) % M);
    return 0;
}