hdu 5177 (1e18范围的卡特兰数)
题意：
求第n个卡特兰数，模3814697265625 (5^18)
限制：
有20组数据，1 <= n <= 1e18
思路：
1. 卡特兰数的表达式：
ans = 1/(n+1) * C(2*n,n)
-> ans = 1/(n+1) * (2n)! / n! / n! ---1式
2. 因为要模5^18，求逆元要求互质，所以先把"1式"中的因子5全部去掉
3. 然后看不含因子5的阶乘，f(n!)
4. 设g(x,n)=(x+1)(x+2)(x+3)(x+4)(x+6)..(x+n)%M，x+d里面的d不是5的倍数
5. 则有f(n!)=g(0,n)*g(0,n/5)*g(0,n/25)*…*g(0,0)%M ---这里需要log(n)的复杂度
6. 对于每个g(x,n)我们可以把g(x,n)分成尽量均匀的两段来计算
part1=(x+1)(x+2)(x+3)(x+4)(x+6)*…*(x+5*k-1)
part2=(x+5*k+1)(x+5*k +2)(x+5*k +3)(x+5*k +4)(x+5*k +6)*…*(x+5*k +5*k-1)
剩余的项直接暴力乘上来就可以了
然后不断地递归下去 ---这里需要log(n)的复杂度
每次计算出part1，通过代入，可以O(1)计算出part2
这里关键的一点是对于每一个多项式，都可以把它化成这样的形式：
a1*x^0 + a2*x^1 + ... + an*x^n ---2式
可以看到，对于g(x,n)，x总是5的倍数，所以对于每一个part，它所生成的"2式"都不会超过18项。 ---这里需要18的复杂度
这道题的复杂度为log(2n)*log(2n)*18+log(n)*log(n)*18。
代码太挫，跑了7300+ms，压线过的，希望有更好写法的大牛们私信我。
hdu 5177 (1e18范围的卡特兰数)
原文：http://blog.csdn.net/whai362/article/details/43909629
