【组合计数】CF1866 H

末蓝、 2024-02-20 09:05 50阅读 0赞

[Problem - H - Codeforces][]

题意

![ae0ad641c2c842abbdd97f19e7c95ea2.png][]

思路

不知道这种trick叫什么，昨天VP刚遇到过

设 f\[x\] 为恰好有一个最大值为 x 的方案数，我们要求这个，那就设 g\[x\] 为 至少有一个最大值为 x 的方案数，那么答案就是 f\[x\] = g\[x\] - g\[x - 1\]

这里也一样，不过要稍微变一下

![e909e9ac09a743d9816381239dbe5411.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 1e6 + 10;
    constexpr int mod = 998244353;
    constexpr int Inf = 0x3f3f3f3f;
    
    int n, k;
    int Fac[N];
    int inv[N];
    int g[N];
    
    int qpow(int a, int b) {
    	int res = 1;
    	while(b) {
    		if (b & 1) res = (res * a) % mod;
    		a = (a * a) % mod;
    		b >>= 1;
    	}
    	return res;
    }
    void Fac_init() {
    	Fac[0] = 1;
    	for (int i = 1; i < N; i ++) {
    		Fac[i] = (Fac[i - 1] * i) % mod;
    	}
    	inv[N - 1] = qpow(Fac[N - 1], mod - 2);
    	for (int i = N - 2; i >= 0; i --) {
    		inv[i] = (inv[i + 1] * (i + 1)) % mod;
    	}
    }
    void solve() {
    	std::cin >> n >> k;
    	for (int i = std::max(0ll, n - k); i <= n; i ++) {
    		g[i] = Fac[n - i + 1] * qpow(n - i + 1, k - (n - i)) % mod;
    	}
    	int ans = 0;
    	for (int i = n; i >= std::max(0ll, n - k); i --) {
    		int res = g[i] - g[i + 1];
    		res *= Fac[n];
    		res %= mod;
    		res *= inv[i];
    		res %= mod;
    		ans += res;
    		ans %= mod;
    	}
    	std::cout << ((ans % mod) + mod) % mod << "\n";
    }
    signed main() {
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    
    	int t = 1;
    	Fac_init();
    	while (t--) {
    		solve();
    	}
    	return 0;
    }

[Problem - H - Codeforces]: https://codeforces.com/contest/1866/problem/H
[ae0ad641c2c842abbdd97f19e7c95ea2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/81fdff59bea64b9eb59034ecfde94da9.png
[e909e9ac09a743d9816381239dbe5411.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c6df6c5ad0ee4eab8e6fd7064ecfbeb8.png