题解 | 小红的连续段

#include <stdio.h>

const int MOD = 1000000007;
const int MAX = 1005; // 对应 x,y <= 1000 的限制

long long fact[MAX];   // 阶乘数组
long long inv[MAX];   // 逆元阶乘数组

// 快速幂：计算 a^b mod MOD
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和逆元阶乘
void init() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    // 逆元：inv[n] = qpow(fact[n], MOD-2)
    inv[MAX - 1] = qpow(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

// 计算组合数 C(n, m)
long long comb(int n, int m) {
    if (m < 0 || m > n) return 0;
    // 公式：C(n,m) = n!/(m!(n-m)!) mod MOD
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int main() {
    // 预处理必须放在 main 开头或调用前
    init(); 
    
    int x, y;
    scanf("%d %d", &x, &y);
    
    long long kind_a[1001] = {0};
    long long kind_b[1001] = {0};
    
    // 插空法：把x个a分成i段 -> C(x-1, i-1)
    for (int i = 1; i <= x; i++) {
        kind_a[i] = comb(x - 1, i - 1);
    }
    // 插空法：把y个b分成i段 -> C(y-1, i-1)
    for (int i = 1; i <= y; i++) {
        kind_b[i] = comb(y - 1, i - 1);
    }
    
    // 枚举总连续段数i
    for (int i = 1; i <= x + y; i++) {
        long long sum = 0;
        if (i == 1) {
            sum = 0;
        } else if (i % 2 == 0) {
            // 偶数：a开头 或 b开头，两种情况，乘2
            int j = i / 2;
            if (j <= x && j <= y) { // 防止越界
                sum = (sum + 2LL * kind_a[j] % MOD * kind_b[j] % MOD) % MOD;
            }
        } else {
            // 奇数：a开头 或 b开头，分别计算
            int j = (i + 1) / 2; // 段数多的一方
            int k = i / 2;       // 段数少的一方
            
            // a开头：a分j段，b分k段
            if (j <= x && k <= y) {
                sum = (sum + kind_a[j] * kind_b[k]) % MOD;
            }
            // b开头：b分j段，a分k段
            if (k <= x && j <= y) {
                sum = (sum + kind_a[k] * kind_b[j]) % MOD;
            }
        }
        printf("%lld\n", sum);
    }
    return 0;
}