BZOJ1856: [Scoi2010]字符串&&Luogu P1641 [SCOI2010]生成字符串

题目描述：

LG传送门
BZOJ传送门

题解：

这题看似有点像DP题，但是其实是一道排列组合题。答案就是C(n+m,m)-C(n+m,m-1)。
详细参考LG上xyz32768的题解

代码如下：

#include<cstdio>
#include<string>
using namespace std;
const int maxn=2000005,tt=20100403;
int n,m;
long long pow[maxn];
long long qsm(long long x,int y){
    long long ret=1,w=x;
    while (y) {
        if (y%2==1) ret=(ret*w)%tt;
        w=(w*w)%tt; y/=2;
    }
    return ret;
}
long long c(int x,int y,int z){
    return 1ll*(pow[x]*qsm(pow[y]*pow[z]%tt,tt-2))%tt;
}
int main(){
    scanf("%d %d",&n,&m);
    pow[0]=1ll;
    for (int i=1;i<=n+m;i++) pow[i]=(1ll*pow[i-1]*i)%tt;
    printf("%lld\n",(c(n+m,n,m)+tt-c(n+m,m-1,n+1))%tt);
    return 0;
}