P1641 [SCOI2010]生成字符串 组合数学
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41603898/article/details/101713303
题意： 现有n个1和m个0 个字符组成的字符串，任意前k个字符1的个数不小于0的个数，求解决方案数，结果对20100403取模。
题解：
è¿éåå¾çæè¿°
（盗图
1和0的个数和为x轴，1和0的个数差为y轴。则需要从（0,0）走到（n+m,n-m），选则1则意味着向右上走一格(1和0的和加1，1和0的差加1)，同理选择0意味着向右下方走一格。 不考虑限制条件，要走n+m步，其中选择 n 步向右上方走，也即C（n+m,n）。 显然里面有不符合规则的，不符合条件的就是和y = -1 有 交点， 如何求不符合方案数？ 将符合条件的向下翻折与 y = -1 相交，然后还要走到 (n+m,n-m)，那么就要在原来基础上多走 1 步，也就是C（n+m,n+1）
ans = C（n+m,n） - C（n+m,n+1）
è¿éåå¾çæè¿°
#include <stdio.h>
#include <iostream>
using namespace std;
const int MOD=20100403;
const int MAXN=3000005;
int fac[MAXN],facinv[MAXN];
long long quickmul(int a,int b) {
long long ret=1;
for(; b ; b >>=1 ,a =(long long) a * a % MOD)
if((b & 1))
ret=ret * a % MOD;
return ret;
}
long long C(int n,int m) {
if(n<0||m<0||n<m)
return 0;
return (long long)fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;
}
void init() {
fac[0]=1;
for(int i=1; i<=MAXN; i++)
fac[i]=(long long)fac[i-1]*i%MOD;
facinv[MAXN]=quickmul(fac[MAXN],MOD-2);
for(int i=MAXN; i>0; i--)
facinv[i-1]=(long long)facinv[i]*(i)%MOD;
//1/(i-1)!=i/(i)!
}
int main() {
init();
int n,m;
scanf("%d %d",&n,&m);
printf("%lld\n",(C(n+m,n)-C(n+m,n+1)+MOD)%MOD);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读