[SCOI2009]游戏

Posted on Edited on In Word count in article: 587 Reading time ≈ 2 mins.
四川省选2009

[SCOI2009]游戏

题目大意

有一个\(1\)到\(n\)的序列, 每个数可能对应另一个数

不停的变换, 直到变回串, 一次变换记作一次花费

问你对于所有可能的对应关系, 有多少种不同的花费 ## 分析 显然, 无论对应关系如何, 这些有对应关系的数一定构成环(包括自环)

对于每一个环, 若他的长度为\(x\), 那么这个环归位的花费一定为\(x\)

那么原串长度可以表示为\(\sum_{i=1}^n len_i\), 那么花费就为\(\mathbb{lcm}len_i\)

所以问题就转化为了有多少种不同的\(\mathbb{lcm}\)

再考虑所有的\(\mathbb{lcm}\), 可以表示为\(\mathbb{lcm}=p_1^{\max(k_1)}p_2^{\max(k_2)}\cdots p_n^{\max(k_n)}\)

看上去是不是有点点像背包了呢?

因为我们知道\(\forall i\;p_i\in[1,n], \forall k\;p_ik\in[1,n]\), 那后每个物品至多选一次(若可以选多次, 那么后面选的不应该有贡献, 如上式), 似乎就可以写一个\(01\)背包了呢

所以我们可以先处理出\(1\sim n\)内所有的素数,再枚举每个素数的\(k\in[1,n]\)次方作为体积为\(p_i^n\)的物品, 容量为\(n\)

就结束啦 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e3 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll f[maxn];
int pr[maxn];
bool vis[maxn];

inline void init()
{
    for (int i = 2; i <= maxn; ++i) {
        if (!vis[i]) pr[++pr[0]] = i;
        for (int j = 1; j <= pr[0] && i * pr[j] <= maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (!(i % pr[j])) break;
        }
    }
}

signed main()
{
    init();
    int n = __read();
    f[0] = 1;
    for (int i = 1; i <= pr[0]; ++i)
        for (int j = n; j >= pr[i]; --j) {//这里的n只能从n到1,保证每个物品只选一次
            int temp = pr[i];
            while (temp <= j) f[j] += f[j - temp], temp *= pr[i];//这里从小到大枚举temp没有什么讲究
            //但是不能先枚举pr[i]的k次方,先枚举次方会导致一个素数被多次计算, 然而他不应该有贡献
        }
    ll ans(0);
    for (int i = 0; i <= n; ++i) ans += f[i];//最后枚举有多少个物品, 从0个物品到n个都是有贡献的
    cout << ans << endl;
    system("pause");
}