洛谷 P1641 [SCOI2010]生成字符串

洛谷

这题一看就是卡塔兰数。

因为(cnt[1] leq cnt[0])，很显然的卡塔兰嘛！

平时我们推导卡塔兰是用一个边长为n的正方形推的，

相当于从(0,0)点走到(n,n)点，向上走的步数不能超过向右走，求出的方案数就是卡塔兰数。

即总方案(-)不合法方案 -> (frac{C_{2n}^{n}}{n+1})。

这题只是改成了从(0,0)走到(n,m)点，那么就是：(C^{m+n}_{n}-C^{m-1}_{m+n})。

因为涉及到除法取模，所以要求逆元。

刚刚好20100403是一个质数，不信可以线性筛一下，所以直接费马小定理求逆元。

code(注意要开long long)：

#include <bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long

const int mo=20100403;
int n,m,ni[2000001]={1},ans;

int qpow(int x,int p)
{
    int d=1;
    while (p) {
        if (p&1) d=d*x%mo;
        x=x*x%mo,p>>=1;
    }
    return d;
}

_int main()
{
    cin>>n>>m;
    for (int i=1;i<=2000000;++i)
        ni[i]=ni[i-1]*i,ni[i]%=mo;
    ans=(ni[m+n]*qpow(ni[m]*ni[n]%mo,mo-2)%mo-ni[m+n]*qpow(ni[m-1]*ni[n+1]%mo,mo-2)%mo+mo)%mo;
    cout<<ans;
    return 0;
}