[SCOI2009]游戏-布布扣-bubuko.com

Time Limit: 1 Sec Memory Limit: 162 MB

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 。

SOLUTION

　　样例中每一列都是由循环节组成的，比如第一列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，有多少种情况。

　　预处理把整数转化为素数幂次的积，然后记忆化搜索。

var prime:array[1..1000]of int64;
    f:array[1..1000,0..1000]of int64;
    n,sum:int64;

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

procedure main;
var i:longint;
begin
     for i:=2 to n do
         if p(i) then
            begin
                 inc(sum);
                 prime[sum]:=i;
            end;
end;

function solve(step,n:int64):int64;
var pow:int64;
begin
     if step>sum 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;

procedure intt;
begin
    assign(input,‘game.in‘);
    assign(output,‘game.out‘);
    reset(input);
    rewrite(output);
end;

procedure outt;
begin
    close(input);
    close(output);
end;

begin
     intt;
     sum:=0;
     readln(n);
     fillchar(f,sizeof(f),char(-1));
     main;
     writeln(solve(1,n));
     outt;
end.

View Code

[SCOI2009]游戏

原文：http://www.cnblogs.com/yangqingli/p/4918690.html