2021牛客寒假算法基础集训营5 比武招亲（上）（组合数学）

Description

图片说明

Solution

本人不擅长组合数学，因此只能打表找规律

map<vector<int>, int> mp;
void dfs(int now, vector<int> v) {
  if (now == m) {
    sort(v.begin(), v.end());
    if (mp[v]) {
      return ;
    }
    mp[v]++;
    ans += v.back() - v[0];
    vis[v.back() - v[0]]++;
    cout << v.back() - v[0] << ' ';
    return ;
  }
  for (int i = 1; i <= n; i++) {
    v.emplace_back(i);
    dfs(now + 1, v);
    v.pop_back();
  }
}
void solve() {
  vector<int> v;
  dfs(0, v);
  for (auto &it : vis) { // 这里可以看出每个数字出现了多少次
    cout << it.first << ' ' << it.second << '\n';
  }
  cout << ans << '\n';
}

本题的答案由两个变量 $n, m$ 决定，直接找规律有难度
因此不妨用控制变量法，即固定 $n$ 的值，对 $m$ 进行变化
不难得到 $n = 2$ 的时候只会出现 $1$ 的贡献, $n = 3$ 的时候只会出现 $1, 2$ 的贡献 ....
于是通过改变 $m$ 的值去看 $n = 2$ 时 $1$ 的贡献随 $m$ 的变化规律， $n = 3$ 时 $1, 2$ 的贡献随 $m$ 的变化规律
不难得到规律:

$1$ 的贡献为 $(m - 1) \cdot (n - 1)$
$2$ 的贡献为 $\frac{m \cdot (m - 1)}{2} \cdot (n - 2)$
$3$ 的贡献为 $\frac{(m + 1) \cdot m \cdot (m - 1)}{6} \cdot(n - 3)$
$\dots$
对于前面分数的分子可以用前缀积 O(1) 计算, 分母是阶乘, 除法取模的时候乘上阶乘的逆元即可。
因为我是用快速幂求逆元，时间复杂度 $O(nlog_2n)$
再预处理下逆元可以 $O(n)$

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 998244353;
int n, m;
int ans = 0;
ll qpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res; 
}

ll M[N], f[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; //cin >> T;
  while(T--) {
    cin >> n >> m;
    M[1] = m - 1; // 前缀积
    for (int i = 2; i <= 5e5; i++) {
      M[i] = M[i - 1] * (m - 2 + i) % mod;
    }
    f[0] = 1; // 阶乘
    for (int i = 1; i <= 5e5; i++) {
      f[i] = f[i - 1] * 1LL * i % mod;
    }
    ll res = 0;
    for (int i = 1; i <= n - 1; i++) {
      res += 1LL * i * M[i] % mod * qpow(f[i], mod - 2) % mod * (n - i) % mod;
      res %= mod;
    }
    cout << res << '\n';
  }
  return 0;
}