【BZOJ1856】[SCOI2010]字符串（组合数学）

题面

题解

把放一个(1)看做在平面直角坐标系上沿着(x)正半轴走一步，放一个(0)看做往(y)轴正半轴走一步，最终的重点就是((n,m))，限制就是不能到达(y=x)上面的部分。
发现这样不好算，我们先考虑一个另外的情况，即(y=x)这个部分也不能到达。
首先发现如果第一步走到了((0,1))，那么方案一定都不合法。
只考虑第一步走到了((1,0))的情况，那么总的方案数就是(C(n+m-1,n-1))
然而有触碰到了(y=x)的情况，我们考虑这条路径第一次碰到(y=x)的时候，然后把前面的所有路径沿着(y=x)翻转，这样子不难发现所有不合法的情况都一一对应到了从((0,1))出发的情况。
所以在(y=x)不能接触的情况下，方案数是(C(n+m-1,n-1)-C(n+m-1,m-1))
现在考虑可以接触(y=x)，简单啊，我们强制你多往右走一步，变成不能接触(y=x)就好了啊。
即(n)变成(n+1)，那么答案就是(C(n+m,n)-C(n+m,m-1))

#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 20100403
#define MAX 1001000
int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
int n,m;
int C(int n,int m)
{
	int s=1,d=1;
	for(int i=n;i>m;--i)s=1ll*s*i%MOD;
	for(int i=n-m;i;--i)d=1ll*d*i%MOD;
	return 1ll*s*fpow(d,MOD-2)%MOD;
}
int main()
{
	cin>>n>>m;
	cout<<(C(n+m,m)+MOD-C(n+m,m-1))%MOD<<endl;
	return 0;
}