卡特兰数列

题目本身很简单，有意识的人会打个表轻易地可以发现是个带除法的取模运算】hnoi2009有趣的数列 收藏

题目本身很简单，有意识的人会打个表轻易地可以发现是个卡特兰数列。

众所周知卡特兰数列的最普通的递推式是O(N^2)的，数据规模是1000000，很显然过不了，卡特兰数列第i项还有另外一个公式就是C(n,2n)/(n+1),这个除法怎么办？我们所知的取模运算是不满足除法的，那应该怎么办？一个最直观的想法就是分解质因数，然后对于每一个质数分别求出它的指数。通过对每个数进行质因数分解是不现实的，复杂度高达O(N^1.3),1000000的数据显然过不了。

ly给了我一个非常漂亮的算法：假设现在我对于数字 i ，要把他的 j 次方加到答案中去，若k是 i 的一个质因子，那么我只要把任务交给k和i/k就可以了，因为i^j=k^j+(i/k)^j,轮到算k或者i/k的时候只要把他的指数+上 j 即可，如果 i 是质数，直接加答案即可，因为最后的答案为整数，那么必定i的指数是正数。

至此我们的任务就只有对于数据规模中的数求出它的一个质因子即可，这让我们想到了复杂度优秀的筛选法（O(N)）,至此此题完美解决，而且算法非常漂亮！！

view plaincopy to clipboardprint? 01.program ex3; 02.var

03. a,b:array[0..2000000] of longint; 04. n,i,p:longint;j,ans:int; 05.function mul(a,b:int):int; 06.begin

07. if b=0 then exit(1);

08. mul:=sqr(mul(a,b>>1)); 09. if odd(b) then mul:=mul*a; 10. mul:=mul mod p; 11.end; 12.begin

13. assign(input,'input.txt');reset(input);

14. assign(output,'output.txt');rewrite(output); 15. readln(n,p);ans:=1; 16. for i:=2 to 2*n do 17. if a[i]=0 then begin 18. j:=i;j:=j*j;

19. while j<=(n<<1) do begin 20. a[j]:=i;inc(j,i); 21. end; 22. end;

23. for i:=2 to n do b[i]:=-1; 24. for i:=n+2 to 2*n do b[i]:=1;

25. for i:=2*n downto 2 do

26. if a[i]=0 then ans:=ans*mul(i,b[i]) mod p 27. else begin

28. inc(b[a[i]],b[i]);

29. inc(b[i div a[i]],b[i]); 30. end; 31. writeln(ans);

32. close(input);close(output); 33.end.

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/jasonzhu8/archive/2010/10/18/5949622.aspx。

众所周知卡特兰数列的最普通的递推式是O(N^2)的，数据规模是1000000，很显然过不了，卡特兰数列第i项还有另外一个公式就是C(n,2n)/(n+1),这个除法怎么办？我们所知的取模运算是不满足除法的，那应该怎么办？一个最直观的想法就是分解质因数，然后对于每一个质数分别求出它的指数。通过对每个数进行质因数分解是不现实的，复杂度高达O(N^1.3),1000000的数据显然过不了。

ly给了我一个非常漂亮的算法：假设现在我对于数字 i ，要把他的 j 次方加到答案中去，若k是 i 的一个质因子，那么我只要把任务交给k和i/k就可以了，因为i^j=k^j+(i/k)^j,轮到算k或者i/k的时候只要把他的指数+上 j 即可，如果 i 是质数，直接加答案即可，因为最后的答案为整数，那么必定i的指数是正数。

至此我们的任务就只有对于数据规模中的数求出它的一个质因子即可，这让我们想到了复杂度优秀的筛选法（O(N)）,至此此题完美解决，而且算法非常漂亮！！

view plaincopy to clipboardprint? 01.program ex3; 02.var

03. a,b:array[0..2000000] of longint; 04. n,i,p:longint;j,ans:int; 05.function mul(a,b:int):int; 06.begin

07. if b=0 then exit(1);

08. mul:=sqr(mul(a,b>>1)); 09. if odd(b) then mul:=mul*a; 10. mul:=mul mod p; 11.end; 12.begin

13. assign(input,'input.txt');reset(input);

14. assign(output,'output.txt');rewrite(output);

15. readln(n,p);ans:=1; 16. for i:=2 to 2*n do 17. if a[i]=0 then begin 18. j:=i;j:=j*j;

19. while j<=(n<<1) do begin 20. a[j]:=i;inc(j,i); 21. end; 22. end;

23. for i:=2 to n do b[i]:=-1; 24. for i:=n+2 to 2*n do b[i]:=1; 25. for i:=2*n downto 2 do

26. if a[i]=0 then ans:=ans*mul(i,b[i]) mod p 27. else begin

28. inc(b[a[i]],b[i]);

29. inc(b[i div a[i]],b[i]); 30. end; 31. writeln(ans);

32. close(input);close(output); 33.end.