Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「SCOI2009」游戏 - 群论 + 背包 DP

windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

{122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

windy 的操作如下:

这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

链接

BZOJ 1025

题解

对于一个置换,我们可以将其分解为若干个循环,问题中的「排数」即为这些循环长度的最小公倍数。设这些循环长度分别为

{x1,x2,,xm} \{ x_1, x_2, \ldots, x_m \}

对于某个 xk x_k 的一个质因子 p p ,它对 lcm(x1,x2,,xm) \mathrm{lcm}(x_1, x_2, \ldots, x_m) 有贡献,当且仅当 p p xk x_k 的唯一分解式中的次数是所有 xi x_i 中最大的。

为了便于统计,我们只考虑每个 xi x_i 都是不同的质数的幂的情况(暂不考虑 xi=1 x_i = 1 的情况)

{x1=p1k1x2=p2k2xm=pmkm \begin{cases} x_1 = p_1 ^ {k_1} \\ x_2 = p_2 ^ {k_2} \\ \cdots \\ x_m = p_m ^ {k_m} \end{cases}

这种情况下,lcm(x1,x2,,xm)=x1×x2××xm \mathrm{lcm}(x_1, x_2, \ldots, x_m) = x_1 \times x_2 \times \ldots \times x_m 。而 {x1.x2,,xm} \{ x_1. x_2, \ldots, x_m \} 是一组合法的循环长度,当且仅当 x1+x2++xm=n x_1 + x_2 + \ldots + x_m = n 。因为我们可以任意添加长度为 1 1 的循环,而不对其最小公倍数产生影响,所以 x1+x2++xmn x_1 + x_2 + \ldots + x_m \leq n 即为合法方案。

现在的问题变成,有一些质数 pi p_i ,每个质数可以不选,也可以选择一个特定的幂 piki p_i ^ {k_i} 。要求最终选择的所有数之和 n \leq n ,求方案总数。这个问题可以转化为分组背包的方案计数问题 —— 第 i i 组物品体积为 pi1,pi2,piki p_i ^ 1, p_i ^ 2, \ldots p_i ^ {k_i} pikin p_i ^ {k_i} \leq n ),背包容量为 n n

代码

#include <cstdio>

const int MAXN = 1000;

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

inline void getPrimes() {
    isNotPrime[0] = isNotPrime[1] = true;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * primes[j] <= MAXN; j++) {
            isNotPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
    // for (int i = 0; i < cnt; i++) printf("%d\n", primes[i]);
}

int main() {
    int n;
    scanf("%d", &n);

    getPrimes();

    static long long f[MAXN + 1][MAXN + 1];
    f[0][0] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int k = 0; k <= n; k++) f[i][k] = f[i - 1][k];
        for (int p = primes[i]; p <= n; p *= primes[i]) {
            for (int k = p; k <= n; k++) {
                f[i][k] += f[i - 1][k - p];
            }
        }
        // for (int k = 0; k <= n; k++) printf("f[%d][%d] = %d\n", i, k, f[i][k]);
    }

    long long ans = 0;
    for (int i = 0; i <= n; i++) ans += f[cnt][i];
    printf("%lld\n", ans);

    return 0;
}