Rockdu's Blog

题目描述

windy学会了一种游戏。

对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。

最开始windy把数字按顺序1，2，3，……，N写一排在纸上。

然后再在这一排下面写上它们对应的数字。

然后又在新的一排下面写上它们对应的数字。

如此反复，直到序列再次变为1，2，3，……，N。

如： 1 2 3 4 5 6

对应的关系为

1->2 2->3 3->1 4->5 5->4 6->6

windy的操作如下

1 2 3 4 5 6

2 3 1 5 4 6

3 1 2 4 5 6

1 2 3 5 4 6

2 3 1 4 5 6

3 1 2 5 4 6

1 2 3 4 5 6

这时，我们就有若干排1到N的排列，上例中有7排。

现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。

输入输出格式

输入格式：

一个整数，N。

输出格式：

一个整数，可能的排数。

输入输出样例

3

3

10

16

说明

30%的数据，满足 1 <= N <= 10 。

100%的数据，满足 1 <= N <= 1000 。

研究过轮换的人都应该熟悉，把两个排列上下的数当成单向边，对应一个由很多环组成的图。

考虑这道题，相当于要从每一个环的一个点同时开始走，然后在一个时间同时回到起点。

问题转化为将n整数拆分的方案中所有方案产生的数集的LCM有多少种。

有一个不那么容易发现的性质(我没发现)：因为可以拆很多1出来，所以只要在N以内的数的整数拆分都是合法方案。因此，如果一个LCM x能被凑出，我们将x分解质因数变成pi^ai乘起来的形式，那么只要pi^ai加起来小于N就行了。因此我们枚举N以内所有质数幂，做一个分组背包就好了。复杂度O(n^2ln n)

#include<cstdio>
#define LL long long
using namespace std;

const int maxn = 1e3 + 5;
int n;
LL dp[maxn];
int pri[maxn], vis[maxn];

void pre(int n) {
    vis[1] = 1;
    for(register int i = 2; i <= n; ++i) {
        if(!vis[i]) pri[++(*pri)] = i;
        for(register int j = 1; j <= *pri && i * pri[j] <= n; ++j) {
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

int main() {
    scanf("%d", &n);
    pre(n), dp[0] = 1;
    for(register int i = 1; i <= *pri; ++i)
        for(register int j = n; j >= 1; --j)
            for(register int k = pri[i]; k <= j; k *= pri[i])
                dp[j] += dp[j - k];
    for(register int i = 1; i <= n; ++i)
        dp[i] += dp[i - 1];
    printf("%lld", dp[n]);
    return 0;
}