「洛谷 P6280」Exercise - DP + 数论

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 \(N\) 头奶牛站成一排。对于 \(1\le i\le N\) 的每一个 \(i\)，从左往右第 \(i\) 头奶牛的编号为 \(i\)。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 \(N (1 \le N \le 10^4)\) 的一个排列 \(A\)，奶牛们改变她们的顺序，使得在改变之前从左往右第 \(i\) 头奶牛在改变之后为从左往右第 \(A_i\) 头。
例如，如果 \(A=(1,2,3,4,5)\)，那么奶牛们总共进行一步。如果 \(A=(2,3,1,5,4)\)，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：

0 步：\((1,2,3,4,5)\)
1 步：\((3,1,2,5,4)\)
2 步：\((2,3,1,4,5)\)
3 步：\((1,2,3,5,4)\)
4 步：\((3,1,2,4,5)\)
5 步：\((2,3,1,5,4)\)
6 步：\((1,2,3,4,5)\)
求所有正整数 \(K\) 的和，使得存在一个长为 \(N\) 的排列，奶牛们需要进行恰好 \(K\) 步。

由于这个数字可能非常大，输出答案模 \(M\) 的余数（\(10^8\le M\le 10^9+7\)，\(M\) 是质数）。

解题思路

我们可以画图理解以下，对于一个序列 \(a_n\)，连有向边 \(i \rightarrow a_i\)。若奶牛需要走 \(k\) 步，则这张图必定成多个环，且所有环的长度的最小公倍数为 \(k\)。

由于与最小公倍数有关，我们可以通过分解质因数解决。于是我们可以先把小于等于 \(n\) 的质数。接下来我们就可以使用 DP 计数。

我么设 \(f_{i, j}\) 表示分解质因数后因数只在前 \(i\) 个质数出现，且点的总数为 \(j\) 的情况下，\(k\) 的总和。于是我们可以推出下列方程（设 \(p_i\) 为第 \(i\) 个质数，总共有 \(\text{cnt}\) 个质数）：

\[ f_{i, j} = f_{i - 1, j} + \sum_{p \in \mathbb{N}^* \wedge p_i^t \le j}{(f_{i - 1, j - p_i^t} \times p_i^t)} \]

如果有剩余的点，我们可以将剩余的点自环解决，这样可不影响最小公倍数。于是我们可以得出答案：\(\sum_{i = 0}^n{f_{\text{cnt}, i}}\)，加上取模即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <climits>
#include <vector>

const int MAXN = 10000;

bool isNotPrime[MAXN + 1];
int primes[MAXN + 1], cnt;

inline void euler() {
    isNotPrime[0] = isNotPrime[1] = true;
    for (int i = 1; i <= MAXN; i++) {
        if (!isNotPrime[i]) primes[++cnt] = i;

        for (int j = 1; j <= cnt; j++) {
            int t = i * primes[j];
            if (t > MAXN) break;

            isNotPrime[t] = true;

            if (i % primes[j] == 0) break;
        }
    }
}


int main() {
    euler();

    int n, m;
    scanf("%d %d", &n, &m);

    while (cnt > 0 && primes[cnt] > n) cnt--;

    std::vector<std::vector<long long>> f(cnt + 1, std::vector<long long>(n + 1));
    f[0][0] = 1;

    for (int i = 1; i <= cnt; i++) {
        for (int j = 0; j <= n; j++) f[i][j] = f[i - 1][j];
        for (int j = primes[i]; j <= n; j++) {
            long long tmp = primes[i];
            while (tmp <= j) {
                f[i][j] = (f[i][j] + f[i - 1][j - tmp] * tmp % m) % m;
                tmp *= primes[i];
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i <= n; i++) ans = (ans + f[cnt][i]) % m;

    printf("%lld\n", ans);

    return 0;
}