Exercise (USACO Gold 2020 US Open)

每次操作就是 $1-N$ 的一个排列，反复进行的话，就会形成若干个环（长度 $C_i$ ），所有环的长度之和为 $N$ 。回到原顺序需要的次数就是 $\text{LCM} C_i$ 。所以问题就是把 $N$ 分成任意多个正整数之和，这些数的LCM unique之后加起来，和是多少。

这时候发现问题还是有一定难度，主要困难是划分方案太多，似乎没有规律，无处下手。我们找找规律，想办法去掉对结果没有贡献的方案，可以有以下发现：

数之间应该互质，否则可以把GCD单独拿出来更优；
每个数应该是单个质数的幂，如果有多个质因子，应该拆开。

这样问题就简单了：就是求由质数幂求和 $\leq N$ 的方案中，所有数乘积的和。这个可以用DP来解， $dp[i][j]$ 定义为: 只使用前面 $i$ 个质数，对于 $j$ 头牛的结果。状态转移也是比较简单的。

复杂度是 $\mathcal{O}(P_N N \log N)$ ，其中 $P_N$ 是小于 $N$ 的质数个数（ $N=10000$ 时为 $1229$ ）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, M, P;
int p[1300];            // all primes <= 1e4
int dp[1300][10005];    // dp[i][j]: with primes p[0..i], result for j cows, 
int ans;
 
bool isprime(int i) {
    bool ok = true;
    for (int j = 2; j <= sqrt(i); j++) {
        if (i % j == 0) {
            ok = false; break;
        }
    }
    return ok;
}
 
int main() {
    scanf("%d %d", &n, &M);
 
    P = 1; p[0] = 1;
    for (int i = 2; i <= n; i++)    // better to use sieve method but this works
        if (isprime(i)) p[P++] = i;
 
    fill(dp[0], dp[0]+n+1, 1);
    for (int i = 1; i < P; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= j; k *= p[i])
                dp[i][j] = (dp[i][j] + (ll)k * dp[i-1][j-(k == 1 ? 0 : k)]) % M;
        }
    }
    printf("%d", dp[P-1][n]);
    return 0;
}