题解 | 小红的连续段

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ll MOD = 1000000007LL;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
#define rep(i,j,k) for(int i=(j);i<(k);i++)
#define per(i,j,k) for(int i=(j);i>(k);i--)

/**
 * @brief 快速幂函数
 */
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

void solve(){
    // Lambda 表达式，创建一个名为 comb_factory 的工厂函数
    auto comb_factory = [&](int max_n) -> function<ll(int, int)> {
        // 先预处理阶乘和阶乘的逆元
        vector<ll> fact(max_n + 1), inv_fact(max_n + 1);
        
        fact[0] = 1;
        for (int i = 1; i <= max_n; ++i) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        inv_fact[max_n] = qpow(fact[max_n], MOD - 2, MOD);
        for (int i = max_n; i >= 1; --i) {
            inv_fact[i - 1] = (inv_fact[i] * i) % MOD;
        }

        //返回一个能计算 C(n, k) 的 Lambda 函数
        return [=](int n, int k) -> ll {
            if (k < 0 || k > n) return 0;
            return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
        };
    };
    
    int x, y; cin >> x >> y;
    int total = x + y;
    auto C_from_example = comb_factory(total);
    for(int i = 1; i <= total; ++i){
        int a1 = (i + 1) >> 1, b1 = i >> 1;
        int a2 = i >> 1, b2 = (i + 1) >> 1;
        ll ans = (C_from_example(x - 1, a1 - 1) * C_from_example(y - 1, b1 - 1)) % MOD;
        ans = (ans + (C_from_example(x - 1, a2 - 1) * C_from_example(y - 1, b2 - 1)) % MOD) % MOD;
        cout << ans << endl;
    }
}

int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}