[SCOI2009]游戏

题目大意

有一个到的序列, 每个数可能对应另一个数

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

问你对于所有可能的对应关系, 有多少种不同的花费

分析

显然, 无论对应关系如何, 这些有对应关系的数一定构成环(包括自环)

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

那么原串长度可以表示为, 那么花费就为

所以问题就转化为了有多少种不同的

再考虑所有的, 可以表示为

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

因为我们知道, 那后每个物品至多选一次(若可以选多次, 那么后面选的不应该有贡献, 如上式), 似乎就可以写一个背包了呢

所以我们可以先处理出内所有的素数,再枚举每个素数的次方作为体积为的物品, 容量为

就结束啦

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