BZOJ1856[Scoi2010]字符串组合数学

Description

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

Input

输入数据是一行，包括2个数字n和m

Output

输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

HINT

【数据范围】
对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000

​​传送门​​

这个数学题有点水了……

1的个数比0大，只有0和1……这很容易引起之前计算卡特兰数的联想

用一个矩阵，行+1代表一个0，列+1代表一个1，

然后统计总的和不合法的方案数再做差……

一个常用套路。

不画图了，​​将狼踩尽的blog​​已经写得非常清楚了。

n不大，直接O(n)求组合数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int 
  N=1000005;
const ll 
  Mod=20100403LL;
ll exgcd(ll a,ll b,ll &x,ll &y){
  if (!b){
    x=1LL,y=0LL;
    return a;
  }
  ll tt=exgcd(b,a%b,x,y),tmp=x;
  x=y,y=tmp-a/b*y;
  return tt;
}
ll C(ll x,ll y){
  ll t1=1LL,t2=1LL,p1,p2;
  for (ll i=1;i<=x;i++) t1=t1*i%Mod;
  for (ll i=1;i<=y;i++) t2=t2*i%Mod;
  for (ll i=1;i<=x-y;i++) t2=t2*i%Mod;
  exgcd(t2,Mod,p1,p2);
  p1=(p1+Mod)%Mod,t1=t1*p1%Mod;
  return t1;
}
int main(){
  ll n,m;cin>>n>>m;
  cout<<(C(n+m,n)-C(n+m,n+1)+Mod)%Mod<<endl;
  return 0;
}