【组合数学】CF1312 D

心已赠人 2024-03-24 18:40 42阅读 0赞

[Problem - 1312D - Codeforces][]

题意：

![ebce078799b24afba8565a369e2f9a80.png][]

![e8b3ab3ae194457bb45c62308c9978d1.png][]

思路：

![22dcb0a2d29b40ada48daec34528001a.jpeg][]

![33c9bc4a29fe46adb646d5dae66f61f1.png][]

![79f287a821c94a47bf70c019ed37bdab.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int M = 2e5 + 10;
    constexpr int mod = 998244353;
    constexpr int Inf = 1e18;
    
    int n, m;
    int Fac[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;
    }
    int inv(int x) {
    	return qpow(x, mod - 2) % mod;
    }
    int C(int n, int m) {
    	return Fac[n] * inv(Fac[m]) % mod * inv(Fac[n - m]) % mod;
    }
    void F_init() {
    	Fac[0] = 1;
    	for (int i = 1; i < N; i ++) {
    		Fac[i] = (Fac[i - 1] * i) % mod;
    	}
    
    }
    void solve() {
    	std::cin >> n >> m;
    	std::cout << C(m, n - 1) * (n - 2)  % mod * qpow(2, n - 2) % mod * inv(2) % mod << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    	F_init();
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - 1312D - Codeforces]: https://codeforces.com/problemset/problem/1312/D
[ebce078799b24afba8565a369e2f9a80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/36bec8bfeb05444081e90d573906d829.png
[e8b3ab3ae194457bb45c62308c9978d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e8a8a3f8d94f4ca796151d77214f0f8e.png
[22dcb0a2d29b40ada48daec34528001a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/a3c1affabd67463ea9e20144d566132d.png
[33c9bc4a29fe46adb646d5dae66f61f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/346a0fc37ce446238ca4f95f08a2d900.png
[79f287a821c94a47bf70c019ed37bdab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c4a4c5dc3ce44ddf8d0a13935b4a6f21.png