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

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

如: 对应的关系为

windy 的操作如下:

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

链接

BZOJ 1025

题解

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

对于某个 的一个质因子 ,它对 有贡献,当且仅当 的唯一分解式中的次数是所有 中最大的。

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

这种情况下,。而 是一组合法的循环长度,当且仅当 。因为我们可以任意添加长度为 的循环,而不对其最小公倍数产生影响,所以 即为合法方案。

现在的问题变成,有一些质数 ,每个质数可以不选,也可以选择一个特定的幂 。要求最终选择的所有数之和 ,求方案总数。这个问题可以转化为分组背包的方案计数问题 —— 第 组物品体积为 ),背包容量为

代码

#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;
}