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，压线过的，希望有更好写法的大牛们私信我。
环境不会改变，解决之道在于改变自己。
