【SCOI 2009】游戏

1025: [SCOI2009]游戏

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 178 Solved: 120
[Submit][Status][Discuss]

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
【数据规模和约定】
30%的数据，满足 1 <= N <= 10 。
100%的数据，满足 1 <= N <= 1000 。

　　看完题目我还以为是游戏论呢……竟然是我最头疼的数学题= =

　　好吧好吧，碰上什么题也得做……首先观察样例：N=6，

　　　　　　　　　　 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-2-3，第二列2-3-1，第三列3-1-2，第四列4-5……那么我们可以知道，如果原数列当中的一个数为i，i所在列的循环节长度为L，那么在经过k*L次变换之后，原来i所在的那一列的数字又将变成i。若要使数列所有位都变回原装态，就要使排列的行数Lines是所有循环节长度的整数倍。

　　如果设循环节长度分别为L1,L2,L2,......,Ln，那么Lines=LCM(L1,L2,L3,......,Ln)。

　　至此，问题被转化成了：给你一个N，问你任意一坨循环节长度的LCM是N，有多少种情况。

　　然后翻了翻班主任给的数论书，发现任意整数可以表示为素数幂次的积（这个分解一下质因数就明白了哈……），然后我们就可以“记忆化搜索”（说他是DP真的有点不舒服）。

　　交了两遍，终于AC了。注意数据范围……

　　那个素数表，本来想从资料库里面复制一个出来……但是估计贴到这里之后就没法看了……于是我从SD08 Point上面Copy了一个打表器用了……

Program SCOI_2009_Game;
var prime:Array[1..168]of longint;
    f:Array[1..168,0..1000]of int64;
    n,cnt:longint;

function IsPrime(x:longint):boolean;
var i:longint;
begin
     for i:=1 to cnt do
         if x mod prime[i]=0 then exit(false);
     exit(true);
end;

procedure Make_Prime_List;
var i:longint;
begin
     for i:=2 to n do
         if IsPrime(i) then
            begin
                 inc(cnt);
                 Prime[cnt]:=i;
            end;
end;

function solve(step,n:longint):int64;
var pow:longint;
begin
     if step>cnt then exit(1);
     if f[step,n]>=0 then exit(f[step,n]);
     solve:=0;
     pow:=prime[step];
     while pow<=n do
           begin
                inc(solve,solve(step+1,n-pow));
                pow:=pow*prime[step];
           end;
     inc(solve,solve(step+1,n));
     f[step,n]:=solve;
end;

begin
     readln(n);
     fillchar(f,sizeof(f),$ff);
     Make_Prime_List;
     writeln(solve(1,n));
     readln;readln;
end.