結果

問題 No.2048 L(I+D)S
ユーザー Khắc Triệu Võ
提出日時 2025-07-06 13:19:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 4,758 bytes
コンパイル時間 2,888 ms
コンパイル使用メモリ 200,504 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-06 13:19:13
合計ジャッジ時間 4,384 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
Author : DeMen100ns (Vo Khac Trieu)
School: University of Science, VNU-HCM
Aim: 
- International Grandmaster Codeforces (2600) 
- ICPC World Final 2025
*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

const long long INF = numeric_limits<long long>::max() / 2;
const int INF_int = 1e9 + 7;

namespace algebra {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 

    template<typename T>
    T bpow(T x, int64_t n) {
        if(n == 0) {
            return T(1);
        } else {
            auto t = bpow(x, n / 2);
            t = t * t;
            return n % 2 ? x * t : t;
        }
    }

    template<int m>
    struct modular {
        // https://en.wikipedia.org/wiki/Berlekamp-Rabin_algorithm
        // solves x^2 = y (mod m) assuming m is prime in O(log m).
        // returns nullopt if no sol.
        optional<modular> sqrt() const {
            static modular y;
            y = *this;
            if(r == 0) {
                return 0;
            } else if(bpow(y, (m - 1) / 2) != modular(1)) {
                return nullopt;
            } else {
                while(true) {
                    modular z = rng();
                    if(z * z == *this) {
                        return z;
                    }
                    struct lin {
                        modular a, b;
                        lin(modular a, modular b): a(a), b(b) {}
                        lin(modular a): a(a), b(0) {}
                        lin operator * (const lin& t) {
                            return {
                                a * t.a + b * t.b * y,
                                a * t.b + b * t.a
                            };
                        }
                    } x(z, 1); // z + x
                    x = bpow(x, (m - 1) / 2);
                    if(x.b != modular(0)) {
                        return x.b.inv();
                    }
                }
            }
        }
        
        int r;
        constexpr modular(): r(0) {}
        constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;}
        modular inv() const {return bpow(*this, m - 2);}
        modular operator - () const {return r ? m - r : 0;}
        modular operator * (const modular &t) const {return (int64_t)r * t.r % m;}
        modular operator / (const modular &t) const {return *this * t.inv();}
        modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
        modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
        modular operator + (const modular &t) const {return modular(*this) += t;}
        modular operator - (const modular &t) const {return modular(*this) -= t;}
        modular operator *= (const modular &t) {return *this = *this * t;}
        modular operator /= (const modular &t) {return *this = *this / t;}
        
        bool operator == (const modular &t) const {return r == t.r;}
        bool operator != (const modular &t) const {return r != t.r;}
        bool operator <  (const modular &t) const {return r < t.r;}
        
        explicit operator int() const {return r;}
        int64_t rem() const {return 2 * r > m ? r - m : r;}
    };

    template <int MOD>
    struct combinatorics{
        int n;
        vector <modular<MOD>> fct, ifct;

        combinatorics(int n): n(n){
            fct.resize(n + 1, 0);
            ifct.resize(n + 1, 0);

            fct[0] = 1;
            for(int i = 1; i <= n; ++i) fct[i] = fct[i - 1] * i;
            ifct[n] = fct[n].inv();
            for(int i = n - 1; i >= 0; --i) ifct[i] = ifct[i + 1] * (i + 1);
        }

        modular<MOD> C(int n, int k){
            if (n < k || k < 0) return 0;
            return fct[n] * ifct[k] * ifct[n - k];
        }

        modular<MOD> Euler(int n, int m){
            //n variables, sum = m
            return C(n + m - 1, m);
        }

        modular<MOD> Catalan(int n){
            return fct[2 * n] * ifct[n] * ifct[n + 1];
        }
    };
    
    template<int T>
    istream& operator >> (istream &in, modular<T> &x) {
        return in >> x.r;
    }
    
    template<int T>
    ostream& operator << (ostream &out, modular<T> const& x) {
        return out << x.r;
    }
};

const int MOD = 998244353;
using namespace algebra;
#define base modular<MOD>

void solve(){
    int n; cin >> n;
    base ans = 0;
    combinatorics <MOD> C(n);
    for(int l = 2, r = n - 2; l <= n && r >= 2; ++l, --r){
        base tmp = C.fct[n] / (C.fct[l - 2] * C.fct[r - 2] * l * r * (n - 1));
        ans += tmp * tmp;
    }
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t = 1; // cin >> t;
    for(int test = 1; test <= t; ++test){
        solve();
    }
}
0