题解 | #小红的连续段#

1. 问题分析

本问题的核心是在给定两种字符（'a' 与 'b'）数量限制的前提下，计算构造出的字符串及其“连续段”数量。

核心约束：

字符数量： 固定包含 $x$ 个 'a' 和 $y$ 个 'b'。
连续段定义： 极长的相同字符序列。这意味着 'a' 的连通块与 'b' 的连通块必须交替出现。
规模： $1 \le x, y \le 1000$ ，这意味着 $O(x \cdot y)$ 或 $O((x+y)^2)$ 的算法复杂度是可接受的。

数学本质： 将 $x$ 个 'a' 分成 $k_a$ 个非空组，将 $y$ 个 'b' 分成 $k_b$ 个非空组。由于两种字符的连续段必须交替排列，因此 $k_a$ 与 $k_b$ 的差值绝对值不可超过 1：

若 $k_a = k_b$ ，字符串形态为 abab... 或 baba...，总连续段 $i = 2k_a$ 。
若 $k_a = k_b + 1$ ，字符串形态为 abab...a，总连续段 $i = 2k_a - 1$ 。
若 $k_b = k_a + 1$ ，字符串形态为 baba...b，总连续段 $i = 2k_b - 1$ 。

2. 组合数学与隔板法

针对上述模型，我们选择组合数学方案而非动态规划，因为该问题可以转化为经典的“隔板法”分配问题。

2.1 隔板法应用

将 $n$ 个相同的元素分成 $k$ 个非空的连续段，等价于在 $n-1$ 个间隔中选择 $k-1$ 个位置放置隔板。方法数公式为： $C(n-1, k-1)$ 。

2.2 状态组合

已知连续段总数为 $i$ ，我们需要枚举所有可能的 $k_a$ 和 $k_b$ 情况：

当 $i$ 为偶数时（ $i = 2k$ ）： 此时必须满足 $k_a = k$ 且 $k_b = k$ 。排列方式有两种：以 'a' 开头（a...b...a...b）或以 'b' 开头（b...a...b...a）。 $Ans(i) = 2 \times C(x-1, k-1) \times C(y-1, k-1)$
当 $i$ 为奇数时（ $i = 2k + 1$ ）： 存在两种互斥情况：
1. 'a' 段比 'b' 段多一段（ $k_a = k+1, k_b = k$ ）：此时必以 'a' 开头且以 'a' 结尾。 $Ways = C(x-1, k) \times C(y-1, k-1)$
2. 'b' 段比 'a' 段多一段（ $k_b = k+1, k_a = k$ ）：此时必以 'b' 开头且以 'b' 结尾。 $Ways = C(x-1, k-1) \times C(y-1, k)$ $Ans(i) = C(x-1, k) \times C(y-1, k-1) + C(x-1, k-1) \times C(y-1, k)$

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;
static constexpr ll MAX_VAL = 1000;

template <ll N>
struct Combination {
    array < array < ll, N + 1 >, N + 1 > data{};

    constexpr Combination() {
        for (int i = 0; i <= N; i++) {
            data[i][0] = 1;
            for (int k = 1; k <= i; k++) {
                data[i][k] = (data[i - 1][k - 1] + data[i - 1][k]) % MOD;
            }
        }
    }

    constexpr ll get(int n, int k) const {
        if (k < 0 || k > n)
            return 0;
        return data[n][k];
    }
};

static const Combination<MAX_VAL> comb;

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

    ll x, y;
    cin >> x >> y;

    for (ll i = 1; i <= x + y; i++) {
        ll k = i / 2;
        ll ans;
        if (i % 2 == 0) {
            ans = 2LL * comb.get(x - 1, k - 1) * comb.get(y - 1, k - 1) % MOD;
        } else {
            ans = comb.get(x - 1, k) * comb.get(y - 1, k - 1) % MOD + comb.get(x - 1,
                    k - 1) * comb.get(y - 1, k) % MOD;
            ans %= MOD;
        }
        cout << ans << endl;
    }
}

4. 复杂度分析

时间复杂度：
- 预计算组合数： $O(N^2)$ ，其中 $N = \max(x, y)$ 。
- 单次查询计算：对于 $i \in [1, x+y]$ 每一个值，计算复杂度为 $O(1)$ ，总计 $O(x+y)$ 。
- 总体复杂度： $O(N^2)$ 。
空间复杂度：
- 组合数存储： $O(N^2)$ 。