#867674 (C++17) No.2327 Inversion Sum

提出ソース

結果

問題	No.2327 Inversion Sum
ユーザー	dyktr_06
提出日時	2023-05-09 21:13:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	22 ms / 2,000 ms
コード長	6,595 bytes
コンパイル時間	2,285 ms
コンパイル使用メモリ	208,132 KB
実行使用メモリ	7,936 KB
最終ジャッジ日時	2024-05-04 18:08:37
合計ジャッジ時間	3,175 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	13 ms 7,808 KB
testcase_01	AC	22 ms 7,936 KB
testcase_02	AC	20 ms 7,808 KB
testcase_03	AC	10 ms 7,168 KB
testcase_04	AC	21 ms 7,296 KB
testcase_05	AC	7 ms 5,376 KB
testcase_06	AC	19 ms 7,808 KB
testcase_07	AC	10 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	22 ms 7,552 KB
testcase_10	AC	6 ms 5,376 KB
testcase_11	AC	7 ms 5,504 KB
testcase_12	AC	5 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	13 ms 5,504 KB
testcase_15	AC	21 ms 6,784 KB
testcase_16	AC	14 ms 7,168 KB
testcase_17	AC	8 ms 6,272 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	13 ms 7,168 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

template <long long Modulus>
struct ModInt{
    long long val;
    constexpr ModInt(const long long &_val = 0) noexcept : val(_val) {
        normalize();
    }
    void normalize(){
        val = (val % Modulus + Modulus) % Modulus;
    }
    inline ModInt& operator+=(const ModInt& rhs) noexcept {
        if(val += rhs.val, val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt& operator-=(const ModInt& rhs) noexcept {
        if(val -= rhs.val, val < 0) val += Modulus;
        return *this;
    }
    inline ModInt& operator*=(const ModInt& rhs) noexcept {
        val = val * rhs.val % Modulus;
        return *this;
    }
    inline ModInt& operator/=(const ModInt& rhs) noexcept {
        val = val * inv(rhs.val).val % Modulus;
        return *this;
    }
    inline ModInt& operator++() noexcept {
        if(++val >= Modulus) val -= Modulus;
        return *this;
    }
    inline ModInt operator++(int) noexcept {
        ModInt t = val;
        if(++val >= Modulus) val -= Modulus;
        return t;
    }
    inline ModInt& operator--() noexcept {
        if(--val < 0) val += Modulus;
        return *this;
    }
    inline ModInt operator--(int) noexcept {
        ModInt t = val;
        if(--val < 0) val += Modulus;
        return t;
    }
    inline ModInt operator-() const noexcept { return (Modulus - val) % Modulus; }
    inline ModInt inv(void) const { return inv(val); }
    ModInt inv(const long long& n) const {
        long long a = n, b = Modulus, u = 1, v = 0;
        while(b){
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= Modulus;
        if(u < 0) u += Modulus;
        return u;
    }
    friend inline ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }
    friend inline ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend inline ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend inline ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }
    friend inline bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val == rhs.val; }
    friend inline bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val != rhs.val; }
    friend inline istream& operator>>(istream& is, ModInt& x) noexcept {
        is >> x.val;
        x.normalize();
        return is;
    }
    friend inline ostream& operator<<(ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

struct Combination{
    vector<long long> memo, memoinv, inv;
    const long long mod;
    Combination(const int &N, const long long &m) : memo(N + 1), memoinv(N + 1), inv(N + 1), mod(m){
        memo[0] = memo[1] = 1;
        memoinv[0] = memoinv[1] = 1;
        inv[1] = 1;
        for(int i = 2; i <= N; ++i){
            memo[i] = memo[i - 1] * i % mod;
            inv[i] = mod - inv[mod % i] * (m / i) % mod;
            memoinv[i] = memoinv[i - 1] * inv[i] % mod;
        }
    }
    inline long long fact(const long long &n) const {
        return memo[n];
    }
    inline long long factinv(const long long &n) const {
        return memoinv[n];
    }
    inline long long ncr(const long long &n, const long long &r) const {
        if(n < r || r < 0) return 0;
        return (memo[n] * memoinv[r] % mod) * memoinv[n - r] % mod;
    }
    inline long long npr(const long long &n, const long long &r) const {
        if(n < r || r < 0) return 0;
        return (memo[n] % mod) * memoinv[n - r] % mod;
    }
    inline long long nhr(const long long &n, const long long &r) const {
        if(n == 0 && r == 0) return 1;
        return ncr(n + r - 1, r);
    }
};

template <typename T>
struct BinaryIndexedTree{
    int N;
    vector<T> BIT;
    BinaryIndexedTree(const int &N): N(N), BIT(N + 1, 0){
    }

    T get(int i){
        return sum(i + 1) - sum(i);
    }

    void add(int i, T x){
        i++;
        while(i <= N){
            BIT[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) const {
        T ans = 0;
        while(i > 0){
            ans += BIT[i];
            i -= i & -i;
        }
        return ans;
    }

    T sum(int L, int R) const {
        return sum(R) - sum(L);
    }

    int lower_bound(T x) const {
        if(x <= 0){
            return 0;
        }else{
            int v = 0, r = 1;
            while(r < N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len < N && BIT[v + len] < x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    int upper_bound(T x) const {
        if(x < 0){
            return 0;
        }else{
            int v = 0, r = 1;
            while(r <= N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len <= N && BIT[v + len] <= x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }
};

const long long MOD = 998244353;

using mint = ModInt<998244353>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<int> c(n, -1), check(n, 1);
    for(int i = 0; i < m; i++){
        int p, k; cin >> p >> k;
        p--, k--;
        c[k] = p;
        check[p] = 0;
    }
    vector<int> sum_c(n + 1), sum_check(n + 1);
    for(int i = 0; i < n; i++) sum_c[i + 1] = sum_c[i] + (c[i] != -1);
    for(int i = 0; i < n; i++) sum_check[i + 1] = sum_check[i] + (check[i]);

    BinaryIndexedTree<mint> BIT(n);
    Combination comb(n, MOD);
    mint ans = 0;
    mint cntc = 0, cntnc = 0;
    for(int i = 0; i < n; i++){
        if(check[i]){
            cntnc += sum_check[n] - sum_check[i + 1];
        }
    }
    
    for(int i = 0; i < n; i++){
        if(c[i] == -1){
            mint plus = comb.fact(n - m - 2);
            plus *= i - sum_c[i];
            plus *= cntnc;
            ans += plus;
            ans += cntc * comb.fact(n - m - 1);
        }else{
            mint plus = sum_check[n] - sum_check[c[i]];
            plus *= comb.fact(n - m - 1);
            plus *= i - sum_c[i];
            ans += plus;
            ans += BIT.sum(c[i] + 1, n) * comb.fact(n - m);

            cntc += sum_check[c[i]];
            BIT.add(c[i], 1);
        }
    }
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード