比赛 CSP2023-S模拟赛 评测结果 RRRRRRRRRRRRRRRRRRRR
题目名称 Maximized Combos 最终得分 0
用户昵称 zxhhh 运行时间 0.010 s
代码语言 C++ 内存使用 10.31 MiB
提交时间 2023-10-17 21:03:42
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5+5, mod = 998244353;
typedef long long ll;
int n, m;  
ll fac[N], inv[N], f[N]; 
ll qpow (ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y&1) res = res*x%mod; 
        x = x*x%mod; y >>= 1;
    }
    return res;
}
ll C (int x, int y) {
    return y > x ? 0 : fac[x]*inv[x-y]%mod*inv[y]%mod; 
}

int main () {
//    freopen("combos.in", "r", stdin); 
//    freopen("combos.out", "w", stdout); 
    cin >> n >> m;
    fac[0] = 1; 
    for (int i = 1;i <= n+1;i++) fac[i] = fac[i-1]*i%mod; 
    inv[n+1] = qpow(fac[n+1], mod-2); 
    for (int i = n+1;i;i--) inv[i-1] = inv[i]*i%mod; 
    f[m] = C(n, m); 
    for (int i = m-1;i >= 1;i--) {
        f[i] = f[i+1]; 
        for (int j = 1;j <= n-m+1;j++) {
            if (n-i*j-j < n-m) break; 
            if (j&1) f[i] -= C(n-m+1, j)*C(n-i*j-j, n-m)%mod; 
            else f[i] += C(n-m+1, j)*C(n-i*j-j, n-m)%mod; 
            f[i] %= mod; 
        }
    }
    for (int i = 1;i <= m;i++) {
        ll ans = f[i]-f[i-1]; ans = ((ans%mod)+mod)%mod; 
        printf("%lld\n", ans); 
    }
    return 0;
}