BZOJ1856 [Scoi2010]字符串（洛谷P1641）

Catalan 逆元

BZOJ题目传送门
洛谷题目传送门

发现这个生成字符串的定义很像Catalan，那么就和Catalan一样搞。

首先总方案数=Cmn+m$=C_{n+m}^m$，关键是求不满足条件的方案数。

Catalan在坐标系中不能超过x轴，而这道题则不能超过直线y=−1$y=-1$，终点为(n+m,n−m)$(n+m,n-m)$。可以发现从(0,0)$(0,0)$走到(x,−1)$(x,-1)$其实相当于从(0,−2)$(0,-2)$走到(x,−1)$(x,-1)$。那么不合法的方案数即为从(0,−2)$(0,-2)$走到(n+m,n−m)$(n+m,n-m)$，等价于Cm−1n+m$C_{n+m}^{m-1}$。则答案为Cmn+m−Cm−1n+m$C_{n+m}^m-C_{n+m}^{m-1}$。

膜的话求个逆元就好了。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000005
#define MOD 20100403
using namespace std;
typedef long long LL;
LL n,m,c[N],iv[N];
inline void Make(){
    c[1]=iv[0]=iv[1]=1;
    for (int i=2;i<=n+m;i++){
        c[i]=(c[i-1]*i)%MOD;
        iv[i]=MOD-(MOD/i)*iv[MOD%i]%MOD;
    }
    for (int i=2;i<=n+m;i++)
        iv[i]=iv[i-1]*iv[i]%MOD;
}
inline LL C (int x,int y){ return c[x]*iv[y]%MOD*iv[x-y]%MOD; }
int main(){
    scanf("%lld%lld",&n,&m),Make();
    printf("%lld\n",((C(n+m,m)-C(n+m,m-1))%MOD+MOD)%MOD);
    return 0;
}