卡特兰数求解及取模优化 - C++ 实现

根据卡特兰数的递推式，可以通过动态规划求解。假设 'dp[i]' 表示第 'i' 个卡特兰数，那么有：/n/n$$dp[i]=/sum_{j=0}^{i-1}dp[j]/times dp[i-j-1]$$ /n/n初始状态为 'dp[0]=1'，最终答案为 'dp[n]'。/n/n时间复杂度为 'O(n^2)'，无法通过本题，可以使用数学方法优化。卡特兰数的通项公式为：/n/n$$C_n=/frac{1}{n+1}/binom{2n}{n}$$ /n/n使用组合数公式可得：/n/n$$/begin{aligned} C_n&=/frac{(2n)!}{(n+1)!n!} // &=/frac{(2n)/times(2n-1)/times/cdots/times(n+2)/times(n+1)}{n/times(n-1)/times/cdots/times2/times1} // &=/prod_{i=1}^n/frac{n+i}{i} /end{aligned}$$ /n/n由于取模运算与乘法运算不满足结合律，无法直接使用乘法计算，需要在计算过程中进行取模操作。为了避免整数溢出，可以使用逆元计算。/n/n具体地，设 'm=10^9'，则有：/n/n$$/begin{aligned} C_n&=/prod_{i=1}^n/frac{n+i}{i} // &=/prod_{i=1}^n/frac{(n+i)/times(n-i+1)}{i/times(n-i+1)} // &=/prod_{i=1}^n/frac{(n+i)}{i}/times/prod_{i=1}^n/frac{(n-i+1)}{n-i+1} // &=/prod_{i=1}^n/frac{(n+i)}{i}/times/prod_{i=1}^n/frac{1}{n-i+1} // &=/frac{(n+1)/times(n+2)/times/cdots/times(2n)}{1/times2/times/cdots/times n}/times/frac{1}{n+1}/times/frac{1}{n+2}/times/cdots/times/frac{1}{2n-n} // &=/frac{1}{n+1}/binom{2n}{n}/bmod m /end{aligned}$$ /n/n时间复杂度为 'O(n)'，可以通过本题。