[SCOI2010]生成字符串 [排列组合]

传送门

放在坐标系里 , 选1为横坐标加1 , 0为纵坐标加1 , 重点是(n,m)

 减去不合法的

解释一下这个图 , 我们将碰到y=x+1 的点翻折 , 原点一定翻折到(-1,1)

也就是说 , 所有从(-1,1)出发的点都是不合法的  , 方案数为 C(n+m,n+1)

#include<bits/stdc++.h>
#define N 2000050
#define p 20100403
#define LL long long
using namespace std;
int n,m; LL fac[N]; 
LL power(LL a,int b){
	LL ans=1; for(;b;b>>=1){if(b&1) ans = (ans*a) % p; a = (a*a) % p;} return ans;
}
LL C(LL x,LL y){
	return ((fac[x] * power(fac[x-y], p-2)) % p * power(fac[y], p-2)) % p;
}
int main(){
	scanf("%d%d",&n,&m); fac[0] = fac[1] = 1;
	for(int i=2;i<=N-50;i++) fac[i] = (LL)(fac[i-1] * i) % p;
	printf("%lld",((C(n+m,n) - C(n+m,n+1)) % p + p) % p); return 0;
}