首页 > > 程序设计 > C/C++ >

bzoj1856 [ SCOI2010 ] -- 卡特兰数

2018-06-17 23:06:41来源：未知阅读 ()

其实就是卡特兰数的定义。。。

将放置一个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 }