結果

問題 No.2327 Inversion Sum
ユーザー Pres1dentPres1dent
提出日時 2023-05-28 16:00:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 14,861 bytes
コンパイル時間 4,412 ms
コンパイル使用メモリ 289,132 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-08 09:12:14
合計ジャッジ時間 8,097 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 RE -
testcase_08 WA -
testcase_09 WA -
testcase_10 RE -
testcase_11 WA -
testcase_12 WA -
testcase_13 RE -
testcase_14 RE -
testcase_15 WA -
testcase_16 RE -
testcase_17 WA -
testcase_18 RE -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 RE -
testcase_24 RE -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 RE -
testcase_29 WA -
testcase_30 RE -
testcase_31 WA -
testcase_32 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include <unistd.h>
using namespace std;
#include "atcoder/all"
using namespace atcoder;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using l_l = pair<i64, i64>;
using d_d = pair<double, double>;
using s_s = pair<string, string>;
using i_i_i = tuple<int, int, int>;
using i_i_i_i = tuple<int, int, int, int>;
using l_l_l = tuple<i64, i64, i64>;
using l_l_l_l = tuple<i64, i64, i64, i64>;
using _bool = int;
#define rep(i, n) for(i64 i = 0; i < n; i++)
#define rep2(i, l, r) for(i64 i = l; i < r; i++)
#define rrep(i, n) for(i64 i = n - 1; i >= 0; i--)
#define rrep2(i, l, r) for(i64 i = r - 1; i >= l; i--)
#define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed)
#define zpad(i) cout << setfill('0') << setw(i)
#define dout cout << fixed << setprecision(10)
#define douts(i) cout << fixed << setprecision(i) << scientific
#define pcnt __builtin_popcount
constexpr int INF = 2147483647;
constexpr i64 I64F = 9223372036854775807;
template <class T> bool chmax(T &l, const T &r) { if (l < r) { l = r; return true; } return false; }
template <class T> bool chmin(T &l, const T &r) { if (l > r) { l = r; return true; } return false; }
template <class T> pair<int, bool> ub(const vector<T> &v, const T &key) { int ind = upper_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rub(const vector<T> &v, const T &key) { int ind = upper_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
template <class T> pair<int, bool> lb(const vector<T> &v, const T &key) { int ind = lower_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rlb(const vector<T> &v, const T &key) { int ind = lower_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
void pu(vector<vector<char>> v) { for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[i].size(); j++) { cout << v[i][j]; } cout << endl; } }
i64 max(i64 l, int r) { return max(l, (i64)r); }
i64 max(int l, i64 r) { return max((i64)l, r); }
void pu(int v) { cout << v << endl; }
void pu(i64 v) { cout << v << endl; }
void pu(double v) { cout << fixed << setprecision(14) << v << endl; }
void pu(ld v) { cout << fixed << setprecision(14) << v << endl; }
void pu(string v) { cout << v << endl; }
void pu(modint998244353 v) { cout << v.val() << endl; }
void pu(modint1000000007 v) { cout << v.val() << endl; }
void pu(vector<int> v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); }
void pu(vector<i64> v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); }
void pu(set<int> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;}
void pu(set<i64> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;}
void pu(multiset<int> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; }
void pu(multiset<i64> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; }
//comb
i64 comb(const i64& n, const i64& k) {
    i64 ret = 1;
    for (i64 i = 1; i <= k; i++) {
        ret *= n + 1 - i;
        ret /= i;
    }
    return ret;
}
struct cord {
    //support coordinate compression
  public:
    cord() : cord(vector<i64> {}) {}
    explicit cord (const vector<i64>& v) : ov(v), cv(v) {
        set<i64> s(v.begin(), v.end());
        int cnt = 0;
        for (auto x : s) { conv[x] = cnt++; }
        for (auto &x : cv) { x = conv[x]; }
        for (auto [k, u] : conv) { rconv[u] = k; }
        conv[I64F] = cnt;
    }
    //ex
    //index            {0, 1, 2, 3, 4, 5}
    //original   value {5, 9, 3, 1, 6, 3}
    //compressed value {2, 4, 1, 0, 3, 1}

    //input:index
    //output:compressed value
    i64 &operator[](int i) {
        assert(0 <= i and i < (int)cv.size());
        return cv[i];
    }

    //input:compressed value
    //output:original value
    i64 get(int v) {
        assert(rconv.find(v) != rconv.end());
        return rconv[v];
    }

    int size() const { return (int)rconv.size(); }

    //input:original value
    //output:index
    int lower_bound(i64 v) { return conv.lower_bound(v) -> second;}

    int upper_bound(i64 v) { return conv.upper_bound(v) -> second;}

  private:
    //original, compressed
    vector<i64> ov, cv;
    //key:original value, value:compressed value
    map<i64, int> conv;
    //key:compressed value, value:origirnal value
    map<int, i64> rconv;
};
//factorial
template<class T> class factorial {
  private:
    vector<T> fact;
    vector<T> ifact;
  public:
    factorial(const int& n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; i--) {
            ifact[i - 1] = ifact[i] * i;
        }
    }
    T comb(const int& n, const int& k) {
        if (k < 0 or k > n) {
            return 0;
        }
        return fact[n] * ifact[k] * ifact[n - k];
    }
    T get(const int& n) { return fact[n]; }
    T inv(const int& n) { return ifact[n]; }
};
//lca
template<class T> struct lca {
  public:
    lca(int n_) : n(n_), to(n), co(n), dep(n), costs(n) {
        l = 0;
        while ((1 << l) < n) { l++; }
        par = vector<vector<int>>(n + 1, vector<int>(l, n));
    }
    void add_edge(int a, int b, T c = 1) {
        to[a].push_back(b);
        co[a].push_back(c);
        to[b].push_back(a);
        co[b].push_back(c);
    }
    void init(int root_ = 0) {
        root = root_;
        dfs(root);
        for (int i = 0; i < l - 1; i++) {
            for (int v = 0; v < n; v++) {
                par[v][i + 1] = par[par[v][i]][i];
            }
        }
    }
    int get(int a, int b) {
        if (dep[a] > dep[b]) { swap(a, b); }
        int gap = dep[b] - dep[a];
        for (int i = l - 1; i >= 0; i--) {
            int len = 1 << i;
            if (gap >= len) {
                gap -= len;
                b = par[b][i];
            }
        }
        if (a == b) { return a; }
        for (int i = l - 1; i >= 0; i--) {
            int na = par[a][i];
            int nb = par[b][i];
            if (na != nb) { a = na, b = nb; }
        }
        return par[a][0];
    }
    T dist(int a, int b) {
        int c = get(a, b);
        return costs[a] + costs[b] - costs[c] * 2;
    }
  private:
    int n, root, l;
    vector<vector<int>> to;
    vector<vector<T>> co; //cost
    vector<int> dep;
    vector<T> costs; //costs sum
    vector<vector<int>> par;
    void dfs(int v, int d = 0, T c = 0, int p = -1) {
        if (p != -1) { par[v][0] = p; }
        dep[v] = d;
        costs[v] = c;
        for (int i = 0; i < to[v].size(); i++) {
            int u = to[v][i];
            if (u == p) { continue; }
            dfs(u, d + 1, c + co[v][i], v);
        }
    }
};
//matrix_ex
template<class T> class matrix_ex {
  private:
    int n;
    vector<vector<T>> rec_relation;
    vector<vector<T>> multipl_sqare(const vector<vector<T>>& lhs,
    const vector<vector<T>>& rhs) {
        vector ret(n, vector<T>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    ret[i][j] += lhs[i][k] * rhs[k][j];
                }
            }
        }
        return ret;
    }
    vector<T> multipl(const vector<vector<T>>& lhs, const vector<T>& rhs) {
        vector<T> ret(n, 0);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                ret[i] += lhs[i][k] * rhs[k];
            }
        }
        return ret;
    }
  public:
    matrix_ex(const vector<vector<T>>& vec_in) : n(vec_in.size()) {
        rec_relation = vector<vector<T>>(n, vector<T>(n));
        rec_relation = vec_in;
    }
    vector<T> get_ans(i64 t, const vector<T>& vec_in) {
        vector ret(n, vector<T>(n, 0));
        for (int i = 0; i < n; i++) {
            ret[i][i] = 1;
        }
        while (t) {
            if ((t % 2LL) == 0LL) {
                rec_relation = multipl_sqare(rec_relation, rec_relation);
                t >>= 1LL;
            } else {
                ret = multipl_sqare(rec_relation, ret);
                t--;    
            }
        }
        return multipl(ret, vec_in);
    }
};
//prime
struct prime {
  public:
    prime() : isp(1e7) {}
    explicit prime (int n) : _n(n), isp(vector<_bool>(n + 1, true)), mfact(vector<int>(n + 1, -1)) {
        isp[0] = isp[1] = false;
        mfact[0] = mfact[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (isp[i]) {
                ps.push_back(i);
                mfact[i] = i;
                for (int j = 2 * i; j <= n; j += i) {
                    isp[j] = false;
                    if (mfact[j] == -1) { mfact[j] = i; }
                }
            }
        }
    }
    vector<l_l> fast_get(int n) {
        vector<l_l> ret;
        assert(0 < n and n <= _n);
        int i = -1;
        while (n > 1) {
            if (i == -1 or ret[i].first != mfact[n]) {
                ret.push_back({mfact[n], 0});
                i++;
            }
            n /= mfact[n];
            ret[i].second++;
        }
        return ret;
    }
    vector<l_l> get(i64 n) {
        vector<l_l> ret;
        assert(0 < n and n <= ps.back() * ps.back());
        int i = 0, cnt = -1;
        while (ps[i] * ps[i] <= n) {
            if (n % ps[i] == 0) {
                ret.push_back({ps[i], 1});
                cnt++;
                n /= ps[i];
                while (n % ps[i] == 0) {
                    n /= ps[i];
                    ret[cnt].second++;
                }
            }
            i++;
            if (i == ps.size()) { break; }
        }
        if (n > 1) ret.push_back({n, 1});
        return ret;
    }
    bool operator[](int n) {
        assert(0 < n and n <= _n);
        return isp[n];
    }
    vector<i64> get_all(i64 n) {
        i64 i = 1;
        vector<i64> ret;
        while (i * i <= n) {
            if (n % i == 0) {
                ret.push_back(i);
                if (n / i != i) { ret.push_back(n / i); }
            }
            i++;
        }
        sort(ret.begin(), ret.end());
        return ret;
    }
  private:
    int _n;
    vector<_bool> isp; //is-prime
    vector<i64> ps; //primes
    vector<int> mfact;
};
//rolling hash
const unsigned bases[64] = {257, 262, 266, 275, 276, 281, 285, 290, 296, 302, 306, 310, 311, 313, 323, 333, 344, 345, 350, 357, 367, 370, 373, 402, 423, 425, 431, 440, 442, 443, 454, 457, 458, 462, 471, 478, 481, 487, 489, 492, 499, 501, 502, 503, 506, 514, 524, 532, 535, 541, 550, 552, 557, 559, 562, 563, 567, 570, 571, 580, 592, 597, 604, 612};
const u64 mod = 0x1fffffffffffffff, base = bases[chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now().time_since_epoch()).count() & 63];
struct rollinghash {
  public:
    rollinghash() : rollinghash("") {}
    explicit rollinghash (const string &s) {
        i64 n = s.size();
        hashed.assign(n + 1, 0);
        power.assign(n + 1, 0);
        power[0] = 1;
        for (i64 i = 0; i < n; i++) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; }
        }
    }

    u64 get(i64 l, i64 r) const {
        u64 ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
        if (ret >= mod) { ret -= mod; }
        return ret;
    }

    u64 connect(u64 h1, u64 h2, i64 h2len) const {
        u64 ret = mul(h1, power[h2len]) + h2;
        if (ret >= mod) { ret -= mod; }
        return ret;
    }

    void connect(const string &s) {
        i64 n = hashed.size() - 1, m = s.size();
        hashed.resize(n + m + 1);
        power.resize(n + m + 1);
        for (i64 i = n; i < n + m; i++) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = mul(hashed[i], base) + s[i - n];
            if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; }
        }
    }

    i64 LCP(const rollinghash &b, i64 l1, i64 r1, i64 l2, i64 r2) {
        i64 len = min(r1 - l1, r2 - l2);
        i64 low = -1, high = len + 1;
        while (high - low > 1) {
            i64 mid = (low + high) / 2;
            if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) { low = mid; }
            else { high = mid; }
        }
        return low;
    }

  private:
    vector<u64> hashed, power;

    static constexpr u64 mask(i64 a) { return (1ull << a) - 1; }

    inline u64 mul(u64 a, u64 b) const {
        u64 a31 = a >> 31, b31 = b >> 31;
        a &= mask(31);
        b &= mask(31);
        u64 x = a * b31 + b * a31;
        u64 ans = (a31 * b31 << 1) + (x >> 30) + ((x & mask(30)) << 31) + a * b;
        ans = (ans >> 61) + (ans & mod);
        if (ans >= mod) { ans -= mod; }
        return ans;
    }
};
template<class T> vector<vector<T>> rot(const vector<vector<T>> &v) {
    vector<vector<T>> ret = v;
    int n = v.size();
    rep(i, n) assert(n == v[i].size());
    rep(i, n) {
        rep(j, n) {
            ret[i][j] = v[j][n - 1 - i];
        }
    }
    return ret;
}
template<class T>void warshall_floyd(T& co) {
    int n = co.size();
    rep(k, n) rep(i, n) rep(j, n) {
        if (co[i][k] == INF) { continue; }
        if (co[k][j] == INF) { continue; }
        chmin(co[i][j], co[i][k] + co[k][j]);
    }
}
// end of template
// *INDENT-ON*
using mint = modint998244353;
int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m; cin >> n >> m;
    factorial<mint> f(n + 1);
    vector<i_i> pk(m);
    rep(i, m) {
        cin >> pk[i].first >> pk[i].second;
    }
    sort(pk.begin(), pk.end());
    fenwick_tree<int> fw(n);
    mint g = 0;
    rep(i, m) {
        fw.add(pk[i].first, 1);
        g += n - pk[i].first;
    }
    mint ans = 0;
    rep(i, m) {
        fw.add(pk[i].first, -1);
        ans += fw.sum(0, pk[i].second);
    }
    vector<mint> t(n + 1);
    t[0] = 0;
    t[1] = 1;
    mint s = 1;
    for (int i = 1; i <= n; i++) {
        s += i;
        t[i + 1] = t[i] + f.get(i - 1) * s;
    }
    ans += t[n - m];
    for (int i = 0; i < m; i++) {
        ans += g * f.get(m - 1);
        g -= n - pk[i].first;
    }
    cout << ans.val() << endl;
    return 0;
}
0