AcWing 889. 满足条件的 01 序列

◎

本节目标

用卡特兰数统计任意前缀中 0 的数量均不少于 1 的数量的 01 序列。

题意与约束

长度为 2n 的序列含 n 个 0 和 n 个 1，且任意前缀中的 0 数量不少于 1 数量，输出这样的序列数模 1_000_000_007。

第一反应与瓶颈

枚举所有 C(2n,n) 个位置选择，再逐个检查前缀，会随 n 指数式增长，无法处理题目上界。

数学关系与算法推导

把 0 看作向右一步、1 看作向上一步。全部从 (0,0) 到 (n,n) 的路径有 C(2n,n) 条；第一次走到对角线错误一侧的路径经反射对应 C(2n,n-1) 条，因此合法数为两者之差。

正确性依据

每条非法路径都有唯一的第一次越界位置，反射越界前的路径段可逆地映射到终点偏移一格的路径；故非法与 C(2n,n-1) 一一对应。相减后既不遗漏也不重复。

样例执行过程

n=3 时全部路径为 C(6,3)=20，非法路径为 C(6,2)=15，答案为 5。测试还将 n≤8 的结果与暴力前缀枚举对拍。

代码实现

C++

C++17

#include <iostream>
using namespace std;

constexpr long long MOD = 1000000007;

long long powerModulo(long long base, long long exponent) {
    long long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) != 0) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exponent >>= 1;
    }
    return result;
}

long long countValidBinarySequences(int n) {
    long long numerator = 1;
    long long denominator = 1;
    for (int value = 1; value <= n; value++) {
        numerator = numerator * (n + value) % MOD;
        denominator = denominator * value % MOD;
    }
    long long chooseMiddle = numerator * powerModulo(denominator, MOD - 2) % MOD;
    long long choosePrevious = n == 0 ? 0 : chooseMiddle * n % MOD * powerModulo(n + 1, MOD - 2) % MOD;
    return (chooseMiddle - choosePrevious + MOD) % MOD;
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    cout << countValidBinarySequences(n) << '\n';
    return 0;
}
#endif

Python

Python 3

import sys


MOD = 1_000_000_007


def power_modulo(base: int, exponent: int) -> int:
    result = 1
    while exponent > 0:
        if exponent & 1:
            result = result * base % MOD
        base = base * base % MOD
        exponent >>= 1
    return result


def count_valid_binary_sequences(n: int) -> int:
    numerator = 1
    denominator = 1
    for value in range(1, n + 1):
        numerator = numerator * (n + value) % MOD
        denominator = denominator * value % MOD
    choose_middle = numerator * power_modulo(denominator, MOD - 2) % MOD
    choose_previous = 0 if n == 0 else choose_middle * n % MOD * power_modulo(n + 1, MOD - 2) % MOD
    return (choose_middle - choose_previous) % MOD


def main() -> None:
    n = int(sys.stdin.buffer.read())
    print(count_valid_binary_sequences(n))


if __name__ == '__main__':
    main()

复杂度分析

连乘计算组合数分子、分母各需 O(n)，求逆元需 O(log MOD)，额外空间 O(1)。

边界与易错点

n=1 的答案是 1。模意义下做减法要加上 MOD 再取模，避免得到负数；分母的逆元依赖质数模数且分母非零。

模式迁移

“任意前缀不能跌破边界”的计数常可尝试路径映射和反射思想；这里不扩展到更复杂的容斥体系。回到组合计数。