首页 > 其他 > 详细

BZOJ 1025. [SCOI2009]游戏

时间:2020-01-23 13:40:39      阅读:84      评论:0      收藏:0      [点我收藏+]

 

根据题意,一种置换的排数就是循环节长度的 $\text{lcm} + 1$。

就变成把 $n$ 个数分成任意多个数,能组成的 $\text{lcm}$ 有多少种。

考虑一个数 $n = p_1 ^ {k_1} p_2 ^ {k_2} \cdots p_m ^{k_m}$ 是否能某些数的 $\text{lcm}$,且这些数的和为 $n$。

当每个数为 $p_1 ^ {k_1}, p_2 ^ {k_2},\cdots, p_m^{k_m}$ 时和最小。

那么就看 $n$ 能被分解成多少种质因子的某次幂之和。但是可以不严格等于 $n$,因为不足 $n$ 可以用 $1$ 来补齐,不影响其 $\text{lcm}$。

那么进行 dp

$dp[i][j]$ 表示前 $i$ 种质因子,和为 $j$ 的方案数,进行分组背包,每种质因数只能用 $p^1, p^2, \cdots, p^m$ 其中的一个。

技术分享图片
#include <bits/stdc++.h>
#define ll long long

const int N = 1e3 + 7;
ll dp[180][N];
int prime[N], prin;
bool vis[N];

void init() {
    static const int XN = 1e3;
    for (int i = 2; i <= XN; i++){
        if (!vis[i]) prime[++prin] = i;
        for (int j = 1; j <= prin && i * prime[j] <= XN; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    init();
    int n;
    scanf("%d", &n);
    dp[0][0] = 1;
    for (int i = 1; i <= prin; i++) {
        for (int j = 0; j <= n; j++)
            dp[i][j] = dp[i - 1][j];
        for (int j = prime[i]; j <= n; j *= prime[i])
            for (int k = j; k <= n; k++) 
                dp[i][k] += dp[i - 1][k - j];
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++)
        ans += dp[prin][i];
    printf("%lld\n", ans);
}
View Code

BZOJ 1025. [SCOI2009]游戏

原文:https://www.cnblogs.com/Mrzdtz220/p/12230525.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!