「BZOJ1025」[SCOI2009]游戏

Description

windy学会了一种游戏。对于11NNNN个数字,都有唯一且不同的11NN的数字与之对应。最开始windy把数字按
顺序112233,……,NN写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们
对应的数字。如此反复,直到序列再次变为112233,……,NN
如: 1 2 3 4 5 6 对应的关系为 121\to2,232\to3, 313\to1,454\to5,545\to4,666\to6
windy的操作如下

1
2
3
4
5
6
7
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想知道,对于所有可能的对应关系,有多少种可
能的排数。

Input

包含一个整数NN

Output

包含一个整数,可能的排数。

Sample Input

1
3

Sample Output

1
10

HINT

1N10001 \leq N \leq 1000

Solution

很显然,置换变化可以写成循环的形式,比如样例可以写成(1 2 3)(4 5)(6)(1\ 2\ 3)(4\ 5)(6)
一个置换变成原来所需的最小步数为lcm(l1,l2,l3,)lcm(l_1,l_2,l_3,\cdots ),其中lnl_n为第nn个循环的长度
那么原题变成:a1+a2++ak=na_1+a_2+\cdots+a_k=nlcm(a1,a2,,ak)lcm(a_1,a_2,\cdots,a_k)个数。
因为pi>1p_i>1,所以p1k1+p2k2++pmkm=np_1^{k_1}+p_2^{k2}+\cdots + p_m^{k_m}=n是满足上述乘积等于tt的最小和。
首先给出一个结论:对于一个t=pikit=\prod p_i^{k_i},其中pip_i是质因数,那么tt是一个合法的lcmlcm当且仅当p1k1+p2k2++pmkmnp_1^{k_1}+p_2^{k2}+\cdots + p_m^{k_m} \leq n

  • p1k1+p2k2++pmkm=np_1^{k_1}+p_2^{k2}+\cdots + p_m^{k_m}=n的时候,显然每一个循环大小分成p1k1,p2k2,,pmkmp_1^{k_1},p_2^{k_2},\cdots ,p_m^{k_m}就行了。
  • p1k1+p2k2++pmkm<np_1^{k_1}+p_2^{k2}+\cdots + p_m^{k_m}<n的时候,显然在上面的基础上,再补几个大小为11的循环就行了
  • 否则,显然就不满足了
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
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1200;

ll f[N][N];
int b[N], tot;
bool vis[N];
void init() {
vis[1] = 1;
for(int i = 2; i <= 1000; ++i) {
if(!vis[i]) b[++tot] = i;
for(int j = 1; j <= tot && i <= 1000 / b[j]; ++j) {
vis[i * b[j]] = 1;
if(i % b[j] == 0) break;
}
}
}
int ksm(int x, int y) {
int res = 1;
for(; y; y>>=1,x=x*x)
if(y&1)res=res*x;
return res;
}
/*
f[i][j]i个质数,目前和为j的方案数
*/
int n;
int main() {
init();
n = read();
f[0][0] = 1;
for(int i = 1; i <= tot; ++i) {
for(int j = 0; j <= n; ++j) {
f[i][j] += f[i - 1][j];
for(int k = 1; ; ++k) {
int t = ksm(b[i], k);
if(j + t > n) break;
f[i][j + t] += f[i - 1][j];
}
}
}
ll ans = 0;
for(int j = 1; j <= n; ++j)
ans += f[tot][j];
writeln(ans + 1);
return 0;
}