M_sea

洛谷1641 [SCOI2010]生成字符串
LuoguBZOJ分析如果只要有 $n$ 个 $1$ 的话,方案数显然是 $C_{n+m}^n$ 。考虑怎么求出不...
扫描右侧二维码阅读全文
14
2019/03

洛谷1641 [SCOI2010]生成字符串

Luogu

BZOJ

分析

如果只要有 $n$ 个 $1$ 的话,方案数显然是 $C_{n+m}^n$ 。

考虑怎么求出不合法的。

想象一个平面直角坐标系,设 $1$ 表示 $(+1,+1)$ , $0$ 表示 $(+1,-1)$ 。

再把经过直线 $y=-1$ 的部分对称一下,看做从 $(0,-2)$ 到 $(n+m,n-m)$ 的方案数,于是就是 $C_{n+m}^{m-1}$ 。

然后答案就是 $C_{n+m}^n-C_{n+m}^{m-1}$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+1;
const int mod=20100403;

int fac[N],inv[N];

inline int qpow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) ans=1ll*ans*a%mod;
    return ans;
}

inline int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main() {
    int n=read(),m=read();
    fac[0]=1;
    for (re int i=1;i<=n+m;++i) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n+m]=qpow(fac[n+m],mod-2);
    for (re int i=n+m;i;--i) inv[i-1]=1ll*inv[i]*i%mod;
    printf("%d\n",(C(n+m,n)-C(n+m,m-1)+mod)%mod);
    return 0;
}
最后修改:2019 年 03 月 14 日 03 : 23 PM

发表评论