UESTC 1282 被兵暴的沈宝宝 Catalan数、逆元

被兵暴的沈宝宝 Catalan数、逆元

Source
UESTC 1282 （CDOJ 1282）

MySolution
卡特兰数经典模型 化简版的递推式是白书上看来的，f2 = f3 = 1 ,卡特兰数从 f3 开始 然后 f(i+1) = (4*i-6)*f(i)/i;
结合拓展欧几里得逆元，inv用的全是LL所以gcd()也把参数全部改成LL了

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int HASH = 1e9+9, maxn = 100006;
int f[maxn];
void gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b) {d = a; x = 1; y = 0;}
    else {gcd(b, a%b, d, y, x); y -= x*(a/b);}
}
LL inv(LL a, LL n)
{
    LL d, x, y;
    gcd(a, n, d, x, y);
    return d == 1 ? (x+n)%n : -1;
}

int main()
{
    f[2] = f[3] = 1;
    long long t;
    for(int i = 3; i <= 100003; i++) {
            if(inv(i, HASH)!= -1){t = 4*i-6; f[i+1] = (t*f[i])%HASH*inv(i, HASH)%HASH;}//有除出现直接逆元，因为虽然可以先搞完再取模，
            //!也许LL不会在这个时候爆，但所使用的是前面的结果，所以必须逆元，然后每个大的*分步取模吧
            else {t = 4*i-6; f[i+1] = (t*f[i])/i%HASH;}  //这句好像用不到☺☺
    }
    //前面没有用逆元 必须除完 i 再取模 ，不然出现 0 的 虽然这样也不对
    //这里多项式取模不会出现负值，  如果其它题目可能会出现负值的话就分开写吧， 就像这样
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        if(n == 1) printf("%d\n", 1);
        else if(n == 0) printf("%d\n", 0);
        else printf("%d\n", f[n+2]);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx