AcWing - 满足条件的01序列(组合数学&卡特兰数)
发布日期:2021-07-01 00:21:43
浏览次数:4
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月08日 09时36分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
PHP中注解(Annotation)的定义与使用
2019-05-02
为什么 Laravel 5 这么好一个框架,国人都不去用?
2019-05-02
使用higncharts 绘制 误差图
2019-05-02
使用highcharts绘制趋势图
2019-05-02
PHP 中 gzuncompress 在 服务器上受限的处理
2019-05-02
PHP 中执行 bat 批处理
2019-05-02
PHP 实现wss协议的WebSocket 客户端
2019-05-02
异步爬虫类
2019-05-02
icePHP框架开发文档-系统配置类-SConfig
2019-05-02
icePHP框架开发文档-全局函数-global
2019-05-02
调用 图灵接口 尝试聊天机器人
2019-05-02
[原]Workerman实际应用
2019-05-02
[原] Python 获取Windows全部硬盘名称
2019-05-02
[原] Python MD5
2019-05-02
[原] Python 根据URL获取JSON
2019-05-02
[原] Python 向文件中追加一行,类似file_put_content
2019-05-02
[原] Python 列表转字典
2019-05-02
[原] Python 日期运算
2019-05-02
[原] Python 判断是否包含中文
2019-05-02