AcWing 889. 满足条件的01序列(卡特兰数应用)

2023-12-24 15:50:27

满足条件的01序列

假设长度为n个序列要求满足题意1的前缀0的个数不能超过1的个数
将问题抽象为从(0, 0)到(n, n)
向上走一个代表这一步对应序列中的值是1,向右走代表序列中的值是0
图来自番茄酱
要想满足1的前缀0的数量大于1的数量就需要满足所有路过的途径在y = x这个函数个下面
但是如何表达呢?
我们采用所有到(n, n)的方案的集合减去越过y = x + 1这个直线的方案集合
因为越过y = x + 1 这个直线的方案集合可以表示为从(0, 0)到(n - 1, n + 1){(n, n)关于 y = x + 1对称的点}的方案集合
而这个答案 C ( n 2 n ) ? C ( n ? 1 2 n ) C\binom{n}{2n} - C\binom{n - 1}{2n} C(2nn?)?C(2nn?1?)
= 2 n ! n ! ? n ! ? 2 n ! ( n + 1 ) ! ( n ? 1 ) ! = \frac{2n!}{n!*n!} - \frac{2n!}{(n + 1)!(n - 1)!} =n!?n!2n!??(n+1)!(n?1)!2n!?

= 2 n ! ? ( n + 1 ) n ! ? ( n + 1 ) ! ? 2 n ! ? n n ! ? ( n + 1 ) ! = \frac{2n!*(n + 1)}{n! * (n + 1)!} - \frac{2n! * n}{n! * (n + 1)!} =n!?(n+1)!2n!?(n+1)??n!?(n+1)!2n!?n?

= 1 ( n + 1 ) 2 n ! n ! ? n ! = \frac{1}{(n + 1)} \frac{2n!}{n!*n!} =(n+1)1?n!?n!2n!?
称为卡特兰数

= C ( n 2 n ) n + 1 = \frac{C\binom{n}{2n}}{n + 1} =n+1C(2nn?)?
2n是x的跨度和y的跨度的和

AcWing 889. 满足条件的01序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;

int qmi(int a, int b, int c)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    int x = 1, y = 1;
    for (int i = 1; i <= 2 * n; i ++) x = (LL)x * i % mod;
    for (int i = 1; i <= n; i ++) y = (LL)y * i % mod;
    //要注意除(n + 1) 也要求逆元因为后面还要% mod
    printf("%lld", (LL) x * qmi(y, mod - 2, mod) % mod * qmi(y, mod - 2, mod) % mod * qmi(n + 1, mod - 2, mod) % mod);
    return 0;
}

文章来源:https://blog.csdn.net/m0_64372178/article/details/135181912
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。