专栏首页wymP1641 [SCOI2010]生成字符串 组合数学

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);

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python随机生成字符串学习

    random.choice从序列中获取一个随机元素。其函数原型为:random.choice(sequence)。参数sequence表示一个有序类型。这里要说...

    py3study
  • 生成N位的数字英文随机混合的字符串

    //随机产生$num位字符串 function mkrandomstr($num=6){ $str="0123456789abcdefg...

    joshua317
  • python生成随机数、随机字符、随机字符串

    本文是基于Windows 10系统环境,实现python生成随机数、随机字符、随机字符串:

    用户7886150
  • swift2.0 字符串,数组,字典学习代码

    swift 2.0 改变了一些地方,让swift变得更加完善,这里是一些最基本的初学者的代码,里面涉及到swift学习的最基本的字符串,数组,字典和相关的操作。...

    Mr.RisingSun
  • java学习之路:8.字符串生成器

    这段代码是照着书上敲的,书上运行结果显示STring 消耗时间:500多,StringBuilder消耗时间:1。

    花狗Fdog
  • 将IP地址字符串分割成数组

        今天心血来潮准备写一个端口扫描器。记得之前写MFC程序里面CString类有个方法可以以某一字符分割CString对象,但是C++中string似乎没有...

    phith0n
  • python无限生成不重复(字母,数字,字符)组合的方法

    以上这篇python无限生成不重复(字母,数字,字符)组合的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持网站事(zalou.cn...

    砸漏
  • PHP常用函数 随机生成字符串

    在平时开发中会用到随机生成授权码,生成账户信息,生成密码,都需要随机字符串的生成,接下来上代码。

    Meng小羽
  • LeetCode 1374. 生成每种字符都是奇数个的字符串

    给你一个整数 n,请你返回一个含 n 个字符的字符串,其中每种字符在该字符串中都恰好出现 奇数次 。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券