对于一个长度为 n n 的序列 A A ，记其置换集合为 G G ，对于 f∈G f \in G ，记使得 的嵌套次数为其排数，求对于所有 f∈G f \in G 共有多少种不同的排数。

题解

将置换改写成轮换，一个很显然的结论是：对于一个置换，所求排数为改写成轮换后所有环的点数的最小公倍数 + 1 1 。

所以问题变为，把 n n 分成 k k 个数 满足 ∑ai=n \sum a_i = n ，求 lcm(ai) \text{lcm}(a_i) 的不同取值个数。

首先要说明一个性质，就是若干个数的最小公倍数一定可以改写成若干个素数的幂的最小公倍数。

以两个数的情况为例：设 k1=a1p1a2p2a3p3 k_1 = a_1 ^ {p_1} a_2 ^ {p_2} a_3 ^ {p_3} ，k2=a1p4a2p5a3p6 k_2 = a_1 ^ {p_4} a_2 ^ {p_5} a_3 ^ {p_6} ，并且 p1>p4,p2<p5,p3>p6 p_1 > p_4, p_2 < p_5, p_3 > p_6 ，那么 lcm(k1,k2)=a1p1a2p5a3p3=lcm(a1p1,a2p5,a3p3) \text{lcm}(k_1, k_2) = a_1 ^ {p_1} a_2 ^ {p_5} a_3 ^ {p_3} = \text{lcm}(a_1 ^ {p_1}, a_2 ^ {p_5}, a_3 ^ {p_3}) 。

当然这个证明不是很严谨啦我也知道不要喷我啦。。这不算是证明只是个说明啦。。其他情况和这种情况也都差不多，所以我们知道，只考虑素数的幂就可以取得所有的不同取值。

考虑DP，以使用不同的素数为阶段，可以满足无后效性，设 f(i,j) f(i, j) 表示目前使用了前 i i 个素数，这些素数的幂的和为 j j 时的不同最小公倍数个数，用类似背包的形式转移，具体转移见代码。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int MAX_N = 1000;
const int MAX_CNT = 168;
bool isNotPrime[MAX_N + 1];
int primes[MAX_N + 1], cnt;
inline void sieve(int n) {
    isNotPrime[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!isNotPrime[i]) primes[++cnt] = i;
        for (int j = 1; j <= cnt && primes[j] * i <= n; j++) {
            int p = primes[j];
            isNotPrime[i * p] = true;
            if (i % p == 0) break;
        }
    }
}
unsigned long long f[MAX_CNT + 1][MAX_N + 1];
int main() {
    int n;
    scanf("%d", &n);
    sieve(n);
    for (int i = 0; i <= cnt; i++) f[i][0] = 1;
    for (int j = 0; j <= n; j++) f[0][j] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            for (int k = primes[i]; k <= j; k *= primes[i]) {
                f[i][j] += f[i - 1][j - k];
            }
        }
    }
    printf("%llu\n", f[cnt][n]);
    return 0;
}