bzoj1856 [ SCOI2010 ] -- 卡特蘭數

其實就是卡特蘭數的定義。。。

將放置一個1視為(1,1)，放置一個0視為(1,-1)

則答案就是從(0,0)出發到(n+m,n-m)且不經過y=-1的方案數。

從(0,0)出發到(n+m,n-m)的總方案數是C(n+m,n)。

若一條路徑經過y=-1，那麼將其從(0,0)到y=-1的一段路徑以y=-1作對稱，就變成了一條從(0,-2)到(n+m,n-m)的路徑。

設走了x步(1,1)，y步(1,-1)，則：x+y=n+m,x-y=n-m+2，解得x=n+1,y=m-1.

那麼答案就是C(n+m,n)-C((n-1)+(m-1),n+1)=C(n+m,n)-C(n+m,n+1)

因為有取模，所以還需要求逆元。

遞推公式：inv[i]=inv[p%i]*(p-p/i)%p，要將inv[0]和inv[1]初始化為1

代碼：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 #define M 20100403
 6 #define ll long long
 7 int i,j,k,n,m,x,y,inv[1000010];
 8 inline int _Max(int x,int y){return x<y?y:x;}
 9 inline ll C(int x,int y){
10     ll Ans=x+1;
11     for(int i=2;i<=y;i++)Ans=(Ans*(x+i)%M)*inv[i]%M;
12     return Ans;
13 }
14 int main()
15 {
16     scanf("%d%d",&n,&m);
17     for(inv[0]=inv[1]=1,i=2;i<=m;i++)inv[i]=1ll*inv[M%i]*(M-M/i)%M;
18     printf("%lld",(C(n,m)-C(n+1,m-1)+M)%M);
19     return 0;
20 }