AcWing - 满足条件的01序列(组合数学&卡特兰数)
发布日期:2021-07-01 00:21:43
浏览次数:3
分类:技术文章
本文共 1368 字,大约阅读时间需要 4 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
给定n个0和n个1,它们将按照某种顺序排成长度为2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。
输出的答案对109+7取模。
输出格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示答案。
数据范围
1≤n≤10^5
输入样例
3
输出样例
5
解题思路
题意:求任意前缀序列中0的个数都不少于1的个数的序列有多少个。
思路:卡特兰数裸题,在2n位序列中填入n个0的方案数为C(2n,n),不填0的其余n位自动填1。从中减去不符合要求(由左而右扫描,1的累计数大于0的累计数)的方案数即为所求。不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m个0的累计数和m+1个1的累计数,此后的2(n-m)-1位上有n-m个0和n-m-1个1。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m-1个0和n-m个1,结果得到一个由n-1个0和n+1个1组成的2n位序列,即一个不合要求的数对应于一个由n-1个0和n+1个1组成的排列。
反过来,任何一个由n-1个0和n+1个1组成的2n位序列,由于0的个数少2个,2n为偶数,所以必定在某一个奇数位上出现1的累计数超过0的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位序列,即n-1个0和n+1个1组成的2n位序列必对应一个不符合要求的数。因而不合要求的2n位序列与n-1个0,n+1个1组成的序列一一对应。
显然,不符合要求的方案数为C(2n,n-1)。由此得出输出序列的总数目为:
,也就是卡特兰数。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;typedef long long ll;const int MOD = 1e9 + 7;int Fast_Power(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; } return res;}int Com_Num(int a, int b, int p) { int res = 1; for (int i = 1, j = a; i <= b; i++, j--) res = 1ll * res * j % p * Fast_Power(i, p - 2, p) % p; return res;}int main() { int n; scanf("%d", &n); printf("%d\n", 1ll * Com_Num(n << 1, n, MOD) * Fast_Power(n + 1, MOD - 2, MOD) % MOD); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99718348 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月09日 14时34分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Request.UrlReferrer为空的问题
2019-05-02
在ASP.NET MVC 中获取当前URL、controller、action
2019-05-02
asp.net中获取当前url的方法
2019-05-02
.net获取用户电脑名,IP,当前电脑用户
2019-05-02
使用C#实现AES加密解密
2019-05-02
C#的DES加密算法
2019-05-02
weblogic各个版本对JDK和Spring的支持度
2019-05-02
Linux中Samba详细安装
2019-05-02
C# Dictionary 泛型字典集合
2019-05-02
C# yyyyMMdd 类型字符串转换为datetime 类型
2019-05-02
JavaScript使用面向对象思想处理cookie .
2019-05-02
Javascript的IE和Firefox兼容性汇编 .
2019-05-02
读GI源码、学JS编程——Javascript动态加载技术。
2019-05-02
JS 精确统计网站访问量程序
2019-05-02
linux Tar 命令参数详解
2019-05-02
linux mkdir 命令详解
2019-05-02
在后台取前台Div或Table的innerHTML或innerText问题
2019-05-02
对表格按日期或数字或字母进行排序的js
2019-05-02
NET中非对称加密RSA算法的密钥保存
2019-05-02