2014年百度之星程序设计大赛

题目链接

分析：打表以后就能发现时卡特兰数， 但是有除法取余。

f[i] = f[i-1]*(4*i - 2)/(i+1);

看了一下网上的题解，照着题解写了下面的代码，不过还是不明白，为什么用扩展gcd, 不是用逆元吗。。

网上还有别人的解释，没看懂，贴一下：

 (a / b) % m = ( a % (m*b)) / b

笔者注：鉴于ACM题目特别喜欢M=1000000007,为质数：

当gcd(b,m) = 1, 有性质: (a/b)%m = (a*b^-1)%m, 其中b^-1是b模m的逆元.

求出b相对于m的逆元b^(-1)，即b*(b^(-1)) = 1 (mod m)。有b*b^(-1) - km = 1，其中k是一整数. 用Extended Euclid算法可以求出`b^(-1)。然后计算a*b^(-1) mod m = ( (a%m) * (b^(-1)%m ) % m; 其值与(a/b) mod m相同

推导：a/b = x (mod m) --两边同乘一个数--> a = bx (mod m) ---x=b^-1a-> a = (b^-1) ba (mod m)

再利用b^-1*b = 1(mod m) . 所以可以得出 x = b^-1*a是成立的。

     所以 (a/b) mod m 的解与 (a*b^-1)%m的解是一样的。 而后着可以利用模对乘法的线性性

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
using namespace std;
const int mo = 1000000000 + 7;
const int maxn = 1000000 + 10;
LL f[maxn];

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1; y=0; return a;
    }
    LL d = exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
void init()
{
    int i;
    LL x, y;
    f[0] = f[1] = 1;
    for(i = 2; i < maxn-5; i++)
    {
        f[i] = f[i-1]*(4*i-2)%mo;
        exgcd(i+1, mo, x, y);
        f[i] = (f[i]*((x+mo)%mo))%mo;
    }
}
int main()
{
    int t, n, ca = 1;
    init();
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("Case #%d:
", ca++);
        printf("%I64d
", f[n]);
    }
    return 0;
}

扩展gcd:

//扩展 GCD  
 //求x, y使得gcd(a, b) = a * x + b * y;  

int extgcd(int a, int b, int & x, int & y)
{ 
    if (b == 0) { x=1; y=0; return a; } 
    int d = extgcd(b, a % b, x, y); 
    int t = x; x = y; y = t - a / b * y; 
    return d; 
}