2018 UESTC Training For Math L 卡特兰数+ 逆元求解

Restaurant
1. 题意：

从 （0，0）走到（n，n）且不经过对角线的方案数。
其实就是卡特兰数。
对于卡特兰数：递归式：
K[ n ]=( ( 4*n-2 )/( n+1 ) )* k[ n-1 ]
2. 思路分析：上面的递推式，代码如下：
3. 核心代码：

之前的多重集排列我们用费马小定理求逆元，是快速幂求解；现在我们是要求 1~n 的所有逆元，如果是快速幂求解的话，复杂度将会是 O( nlog(p) ),p 很大时会TLE，考虑递推式：
Inv[ n ]=( M-M/n )*inv[ M%n ]%M ;
即可在线性时间内求解。最后输出我们的结果即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ULL unsigned long long
using namespace std;

long long n;
const long long M=1000000007;
long long inv[1000010];
long long last,now=1;

void init()
{
    inv[1]=1;
    for(int i=2;i

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net