BZOJ1856[Scoi2010]字符串——组合数学+容斥-白红宇

BZOJ1856[Scoi2010]字符串——组合数学+容斥

阅读量：6454 次

发布时间：2019-06-23

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

题目描述

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

输入

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

输出

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

样例输入

2 2

样例输出

提示

【数据范围】

对于30%的数据，保证1<=m<=n<=1000

对于100%的数据，保证1<=m<=n<=1000000

将选$1$看成往右走，选$0$看成往上走，那么要求的就是从$n*m$的网格的左下角走到右上角且不能穿过$y=x$的方案数。

将不能穿过$y=x$看成不能走到$y=x+1$，答案就是总方案数(即没有不能穿过$y=x$限制的方案数)-走到$y=x+1$的方案数。

将起点关于$y=x+1$对称到$(-1,1)$，那么走到$y=x+1$的方案数就是从$(-1,1)$走到$(n,m)$只能往右和往上走的方案数。

最终答案就是$C_{n+m}^{n}-C_{n+m}^{n+1}$，注意当$n<m$时答案为$0$。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;const int mod=20100403;int n,m;int fac[2000010];int inv[2000010];int C(int n,int m){ return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}int main(){ scanf("%d%d",&n,&m); inv[0]=inv[1]=fac[0]=fac[1]=1; for(int i=2;i<=n+m;i++) { fac[i]=1ll*fac[i-1]*i%mod; inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; } for(int i=2;i<=n+m;i++) { inv[i]=1ll*inv[i-1]*inv[i]%mod; } if(n>=m) { printf("%d",(C(n+m,n)-C(n+m,n+1)+mod)%mod); } else { printf("0"); }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10954692.html

你可能感兴趣的文章