博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ1856: [Scoi2010]字符串
阅读量:5304 次
发布时间:2019-06-14

本文共 1314 字,大约阅读时间需要 4 分钟。

Description

lxhgww最近接到了一个生成字符串的任务,任务需要他把n个1和m个0组成字符串,但是任务还要求在组成的字符串中,在任意的前k个字符中,1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个,聪明的程序员们,你们能帮助他吗?

Input

输入数据是一行,包括2个数字n和m

Output

输出数据是一行,包括1个数字,表示满足要求的字符串数目,这个数可能会很大,只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

HINT

【数据范围】

对于30%的数据,保证1<=m<=n<=1000
对于100%的数据,保证1<=m<=n<=1000000

蒟蒻表示只会nk的DP,承担不起
根据题解考虑转化模型,变为从(0,0)走到(n+m,n-m),1表示斜向上走比如(0,0)走到(1,1),0则相反
那么总数为C(n+m,m),再考虑错误情况
那就是走到过-1的这些情况,那么对-1取对称,其实就是跑了y轴中-2往上的情况
走到(n+m,n-m)需要向上走n-m+2次,一共要走n+m次。设向上向下各走x,y,
那么x+y=n+m,x-y=n-m+2得到x=n+1,y=m-1,所以不合法的方案为C(n+m,m-1)
实力太弱实在无力
代码如下:
//MT_LI#include
#include
#include
#include
#include
using namespace std;typedef long long ll;ll mod=20100403ll;int n,m;ll pow_mod(ll a,ll b){ ll ans=1ll; while(b) { if(b&1)ans=ans*a%mod; b/=2;a=a*a%mod; } return ans;}ll fac[2100000];void init(){ fac[1]=1ll; for(ll i=2;i<=2000000;i++) fac[i]=fac[i-1]*i%mod;}int main(){ init(); scanf("%d%d",&n,&m); printf("%lld\n",(fac[n+m]*pow_mod(fac[n],mod-2)%mod*pow_mod(fac[m],mod-2)%mod-fac[n+m]*pow_mod(fac[m-1],mod-2)%mod*pow_mod(fac[n+1],mod-2)%mod+mod)%mod); return 0;}

 

转载于:https://www.cnblogs.com/MT-LI/p/9869753.html

你可能感兴趣的文章
css背景样式
查看>>
JavaScript介绍
查看>>
开源网络漏洞扫描软件
查看>>
yum 命令跳过特定(指定)软件包升级方法
查看>>
创新课程管理系统数据库设计心得
查看>>
Hallo wolrd!
查看>>
16下学期进度条2
查看>>
Could not resolve view with name '***' in servlet with name 'dispatcher'
查看>>
Chapter 3 Phenomenon——12
查看>>
C语言中求最大最小值的库函数
查看>>
和小哥哥一起刷洛谷(1)
查看>>
jquery对id中含有特殊字符的转义处理
查看>>
遇麻烦,Win7+Ubuntu12.10+Archlinux12.10 +grub
查看>>
SqlBulkCopy大批量导入数据
查看>>
pandas 修改指定列中所有内容
查看>>
「 Luogu P2285 」打鼹鼠
查看>>
lua语言入门之Sublime Text设置lua的Build System
查看>>
vue.js基础
查看>>
电脑的自带图标的显示
查看>>
[转载] redis 的两种持久化方式及原理
查看>>