AcWing 889 满足条件的01序列
发布日期:2021-05-28 16:27:12 浏览次数:9 分类:技术文章

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

题目描述:

给定n个0和n个1,它们将按照某种顺序排成长度为2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。输出的答案对10^9+7取模。

输出格式

共一行,包含整数n。

输出格式

共一行,包含一个整数,表示答案。

数据范围

1≤n≤10^5

输入样例:

3

输出样例:

5

分析:

将题目的1看作进栈,0看作出栈,任何时候出栈次数不能大于进栈次数,则本题可看做求栈混洗合法序列的数目。或者将1看作左括号,0看作右括号,就等价于括号匹配的合法数目了,故本题等价于求Catalan(n) = C(2n,n) / (n+1)。除法运算由于模数10^9 + 7是素数,故可以使用快速幂求乘法逆元来变成乘法运算。

卡特兰数公式的推导:可看作从坐标系中原点前进到(n,n)点的走法,1表示向右移动一格,0表示向上移动一格。如果没有限制的话相当于在2n步中选n步向右,一共C(2n,n)种走法,但是1的个数要始终大于0的个数说明走的轨迹要始终不能超过y = x这条直线,准确地说是不能触碰到y = x + 1这条线。一旦触碰到了,设第一次在x点触碰到了y = x + 1,则之后的轨迹的终点也是(n,n),将x到终点的路径关于y = x + 1做轴对称,得到另一条路径,终点是(n - 1,n + 1)。故任意一条触碰到y = x + 1的非法路径都可以转化为终点为(n - 1,n + 1)的路径,一共是C(2n,n - 1)种非法路径,故合法路径一共是C(2n,n) - C(2n,n - 1)。C(2n,n - 1) = (2n)! / ((n-1)! * (n + 1)!) = n / (n + 1) * (2n)! / (n! * n!) = n / (n + 1) * C(2n,n),故Catalan(n ) = C(2n,n) / (n + 1)。

#include 
using namespace std;typedef long long ll;const int mod = 1e9 + 7;int qmi(int a,int k,int p){ int res = 1; while(k){ if(k & 1) res = (ll)res * a % p; a = (ll)a * a % p; k >>= 1; } return res;}int main(){ int n; cin>>n; int res = 1; for(int i = 2 * n,j = 1;j <= n;i--,j++){ res = (ll) res * i % mod; res = (ll) res * qmi(j,mod - 2,mod) % mod; } res = (ll)res * qmi(n + 1,mod - 2,mod) % mod; cout<
<

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/103817537 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 890 能被整除的数
下一篇:AcWing 888 求组合数 IV

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年02月25日 16时54分37秒