【枚举+推式子】牛客小白月赛 63 E

淡淡的烟草味﹌ 2024-03-23 22:04 42阅读 0赞

[登录—专业IT笔试面试备考平台\_牛客网][IT]

题意：

![effad702cb0d48cd8c6dfbdc3dff77f0.png][]

![adbb25f7272a45798bfec20fd9b2b3ec.png][]

思路：

首先是个计数问题，考虑组合数学

组合数学就是在考虑枚举所有包含1和n的区间

这个典中典就是枚举1和n的位置然后算贡献

双指针超时，考虑推式子：

![4013bd4bf0cb4b41a60c6f9ebd021d43.jpeg][]

Code：

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

[IT]: https://ac.nowcoder.com/acm/contest/49030/E
[effad702cb0d48cd8c6dfbdc3dff77f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fa15c4a0936e4edbbd614f06a9ad4fb0.png
[adbb25f7272a45798bfec20fd9b2b3ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9383e1311a8e426796ffa8ab11858bfc.png
[4013bd4bf0cb4b41a60c6f9ebd021d43.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8fc76dd5341b4ce28ca001b1950cf695.png