Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 1025」「SCOI2009」游戏

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

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

Input

包含一个整数N,1 <= N <= 1000

Output

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

Sample Input

【输入样例一】

1
3

【输入样例二】

1
10

Sample Output

【输出样例一】

1
3

【输出样例二】

1
16

Solution

OEIS 题。

本题等价于对于每个 0..n 中的数求有多少种拆分成若干个质数的乘方之和的方法,然后再求和。

具体地说,一个置换方案的「排数」就是该置换各个循环节的长度的 LCM+1。然后问题变为 n 拆分成若干数(不一定是质数)之和,其 LCM 有多少种情况。

定理:当且仅当 $\sum {p_i}^{a_i} \le n$ 时,$\prod {p_i}^{a_i}$ 是一个可能的 LCM,其中 $\{p_i\}$ 为互不相同的质数。

所以本题可以用一个非常简单的 DP 求解。预处理 n 以内的质数,然后枚举乘方转移,类似背包 DP。

质数有 $n/\ln(n)$ 个,而每个质数对每个状态转移至多 $\log_p n$ 次,所以总时间复杂度为 $O(n^2)$。

详细信息参见 http://oeis.org/A009490。这里面还介绍了本题的生成函数公式,然而对于这道特定的题目而言有些小题大做了……

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
#include <bits/stdc++.h>
using namespace std;
#define long long long
const int maxn = 1005;
int n, prime[maxn], pcnt;
long dp[maxn][maxn];
bool vis[maxn];
void euler_prime() {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) prime[++pcnt] = i;
for (int j = 1; j <= pcnt; ++j) {
int v = i * prime[j];
if (v > n) break;
vis[v] = true;
if (i % prime[j] == 0) break;
}
}
}
int main() {
scanf("%d", &n);
euler_prime();
for (int i = 0; i <= pcnt; ++i) dp[i][0] = 1;
for (int i = 1; i <= n; ++i) dp[0][i] = 1;
for (int i = 1; i <= pcnt; ++i) {
int p = prime[i];
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i - 1][j];
for (int x = p; x <= j; x *= p) dp[i][j] += dp[i - 1][j - x];
}
}
printf("%lld\n", dp[pcnt][n]);
return 0;
}
最近的文章

「BZOJ 2306」「CTSC2011」幸福路径

Description有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i)。现在有一只蚂蚁,从给定的起点 v0出发,沿着图 G 的边爬行。开始时,它的体力为 1。每爬过一条边,它的体力都会下降为原来的 ρ 倍,其中ρ 是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度,是它…

BZOJ, Floyd, 倍增 继续阅读
更早的文章

「BZOJ 3864」「HDU 4899」Hero meet devil

DescriptionThere is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king u…

BZOJ, DP 套 DP, HDOJ, 序列 DP 继续阅读