发现这是一道DP组合数学题。
我们考虑在坐标系里看问题。我们每次将(x)坐标加1,如果这里是(1)就(y)坐标加1,否则减1,就得到了一条起点是((0,0)),终点是((n+m,n-m))的折现。
比如下面两个01串:
我们发现蓝色的折线是合法的,红色不合法,因为红色折线和直线(y=-1)有交点。
我们还发现,这样的折线一共有(C_{n+m}^n)条(组合意义上就是在(n+m)个位置中选择(n)个位置放1,其他放0)。
我们发现答案就是(C_{n+m}^n-( exttt{不合法折线数量}))。
考虑后者怎么求。
我们可以把任意不合法折线第一次与(y=-1)相交位置之前的部分以(y=-1)为对称轴翻转,就得到了一条起点为((0,-2)),终点为((n+m,n-m))的折线,并且前后者显然一一对应。
我们发现后者有(C_{n+m}^{n+1})条(这是因为这条折线对应的01串里有(n+1)个1和(m-1)个0),所以前者也有那么多。
那么答案就是(C_{n+m}^n-C_{n+m}^{n+1})。
直接根据公式(C_n^m=frac{n!}{m!(n-m)!})算出即可。
另:20100403是一个质数,所以(x)在(mod 20100403)意义下的逆元就是(x^{20100401})。
code:
#include<bits/stdc++.h>
using namespace std;
const long long mod=20100403;
long long n,m;
long long POW(long long x,long long y){
long long tot=1;
while(y){
if(y&1)tot=tot*x%mod;
x=x*x%mod;
y/=2;
}
return tot;
}
long long fac(long long x){
long long tot=1;
for(int i=2;i<=x;i++)tot=tot*i%mod;
return tot;
}
long long C(long long x,long long y){
return fac(x)*POW(fac(y)*fac(x-y)%mod,mod-2)%mod;
}
int main(){
scanf("%lld%lld",&n,&m);
printf("%lld",(C(n+m,n)-C(n+m,n+1)+mod)%mod);
return 0;
}