一、核心数学原理

1. 连续段的拆分规律
  • x 个 'a' 要分成 p 个连续段：需要在 x-1 个相邻 'a' 之间的间隙中选 p-1 个位置分割，方法数为组合数 C(x-1, p-1)（比如 2 个 a 分成 1 段：C(1,0)=1；分成 2 段：C(1,1)=1）。
  • y 个 'b' 要分成 q 个连续段：同理，方法数为 C(y-1, q-1)。
  • 总连续段数 i = p + q，且 |p - q| ≤ 1（否则字符段会断层，比如 a 分 3 段、b 分 1 段，无法交替排列）。
2. 两种合法排列情况

总段数为 i 时，只有两种可能：

  • 情况 1：p = (i+1)/2，q = i/2（a 段数比 b 多 1，字符串以 a 开头、a 结尾）；
  • 情况 2：p = i/2，q = (i+1)/2（b 段数比 a 多 1，字符串以 b 开头、b 结尾）；
  • 两种情况的方法数相加，即为总答案。

二、代码实现思路

1. 预处理组合数（阶乘 + 逆元）

由于 x,y ≤ 1000，需要预处理阶乘 fac[] 和逆元阶乘 infac[]，快速计算组合数 C(n, k)：

  • 组合数公式：C(n, k) = fac[n] * infac[k] * infac[n-k] % MOD（MOD=1e9+7）；
  • 逆元计算：利用费马小定理，a 的逆元为 ksm(a, MOD-2, MOD)（MOD 是质数）。
2. 核心计算逻辑

对每个 i ∈ [1, x+y]，计算：

plaintext

ans[i] = (C(x-1, p1-1)*C(y-1, q1-1) + C(x-1, p2-1)*C(y-1, q2-1)) % MOD

其中：

  • p1 = (i+1)/2，q1 = i/2（a 段多 1）；
  • p2 = i/2，q2 = (i+1)/2（b 段多 1）；
  • 若 p1>x 或 q1>y，则该情况贡献为 0；同理处理 p2/q2。

int fac[M];
int infac[M];
void init()
{
    fac[0] = 1;
    for (int i = 1; i < M; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
    infac[M - 1] = ksm(fac[M - 1], MOD - 2, MOD);
    for (int i = M - 2; i >= 0; i--)
    {
        infac[i] = infac[i + 1] * (i + 1) % MOD;
    }
}
int C(int x, int k)
{
    if (k > x || k < 0)
        return 0;
    return fac[x] * infac[x - k] % MOD * infac[k] % MOD;
}
void solve()
{
    cin >> x >> y;
    for (int i = 1; i <= x + y; i++)
    {
        cout << (C(x - 1, (i + 1) / 2 - 1) * C(y - 1, i / 2 - 1) + C(x - 1,i / 2 - 1) *C(y - 1, (i + 1) / 2 - 1)) % MOD << '\n';
    }
}