「BZOJ1025」[SCOI2009] 游戏

2014年9月13日6,9730

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。

Output

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

Sample Input

「输入样例一」
3
「输入样例二」
10

Sample Output

「输出样例一」
3
「输出样例二」
16

HINT

「数据规模和约定」

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

题解

wulala：

这道题可以转换一下。

试想每一个对应关系a-b为从a->b的一条边，

那么图中一定存在n条边且每个点入度出度都为1，

易证一定存在一个或几个环。

实际上排数就是这几个环大小的最小公倍数。

即求和为n的数列的最小公倍数种数。

那么可以直接DP

 

avatar
  Subscribe  
提醒