NC9985B比武招亲(上)

Solution

1. 枚举贡献,当前的数量为个。
2. 对于贡献挑选的有对，
3. 对于确定的情况有多少种的选法问题，其实等价于个不同的盒子里放个相同的小球，有多少种放法。
   下面求个盒子里放个相同的小球，有多少种放法，这本质就是重复组合的问题。
   有种方法，具体可以看重复组合的定义和证明。
   将代入，对于确定的情况有种选法。

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll mod = 998244353;
constexpr ll N = 1e6 + 5;

ll fac[N + 5], ifac[N + 5];

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

inline ll perm(ll x, ll y) { return y > x || y < 0 ? 0 : fac[x] * ifac[x - y] % mod; }

inline ll comb(ll x, ll y) { return y > x || y < 0 ? 0 : perm(x, y) * ifac[y] % mod; }

void init() {
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = 1ll * i * fac[i - 1] % mod;
    ifac[N] = qpow(fac[N], mod - 2);
    for (int i = N; i; i--) ifac[i - 1] = 1ll * i * ifac[i] % mod;
}

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

    init();
    ll n, m, ans = 0, base = 0;
    cin >> n >> m;
    for (int i = 1; i <= n - 1; i++) {
        ans = (ans + 1ll * i * (n - i) % mod * comb(m + i - 2, m - 2) % mod) % mod;
    }
    cout << ans << '\n';

    return 0;
}