提出 #75598395

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int mod = 998244353;
int fix(int x){
    x%=mod;
    if(x<0)x+=mod;
    return x;
}

struct SegTree {
    typedef ll T; T idT = {};
    typedef ll U; U idU = 1;
    // combining segtree nodes a and b
    T f(T a, T b) { return fix(a+b); }
    // applying updates a and b (in that order)
    U g(U b, U a) { return fix(a*b); }
    // applying update b to segtree node a
    T h(U b, T a) { return fix(a*b); }
    int n;
    vector<T> t;
    vector<U> d;
    SegTree(int n) : n(n), t(2*n, idT), d(n, idU) {}
    void calc(ll p) { t[p] = h(d[p], f(t[p*2], t[p*2+1])); }
    void apply(ll p, U v) {
        t[p] = h(v, t[p]);
        if(p < n) d[p] = g(v, d[p]);
    }
    void push(ll p) { /// start-hash
        p += n;
        for(int s = 19; s > 0; s--){
            ll i = p >> s;
            if(d[i] != idU) {
                apply(i * 2, d[i]);
                apply(i * 2 + 1, d[i]);
                d[i] = idU;
            }
        }
    } /// end-hash
    void modify(ll p, T v) { /// start-hash
        push(p);
        t[p += n] = v;
        while(p > 1) calc(p /= 2);
    } /// end-hash
    void modify(ll l, ll r, U v) { /// start-hash
        push(l), push(r - 1);
        bool cl = false, cr = false;
        for(l += n, r += n; l < r; l /= 2, r /= 2) {
            if(cl) calc(l - 1);
            if(cr) calc(r);
            if(l & 1) apply(l++, v), cl = true;
            if(r & 1) apply(--r, v), cr = true;
        }
        for(--l; r; l /= 2, r /= 2) {
            if(cl) calc(l);
            if(cr) calc(r);
        }
    } /// end-hash
    T query(ll l, ll r) { /// start-hash
        push(l), push(r - 1);
        T resl = idT, resr = idT;
        for(l += n, r += n; l < r; l /= 2, r /= 2) {
            if(l & 1) resl = f(resl, t[l++]);
            if(r & 1) resr = f(t[--r], resr);
        }
        return f(resl, resr);
    } /// end-hash
};

const int MXN = 10005;
vector<int>fact(MXN+10);
vector<int>inv(MXN+10);
int modpow(int x, int y) {
    return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}
int choose(int x, int y){
    if(y>x || x < 0 || y < 0)return 0;
    return (fact[x]*inv[y]%mod)*inv[x-y]%mod;
}
int permute(int x, int y){
    if(y>x || x < 0 || y < 0)return 0;
    return (fact[x]*inv[x-y])%mod;
}
void precalc(){
    fact[0] = 1; inv[0] = 1;
    for(int i = 1; i<=MXN; i++){
        fact[i] = fact[i-1]*i%mod;
    }
    inv[MXN] = modpow(fact[MXN],mod-2);
    for(int i = MXN-1; i>0; i--){
        inv[i] = inv[i+1]*(i+1)%mod;
    }
}
int inverse(int x){
    return modpow(x,mod-2);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0); precalc();
    int n,m;
    cin >> n >> m;
    vector<vi>adj(m+5);
    for(int i = 1; i<=n; i++){
        int l,r;
        cin >> l >> r;
        adj[r].push_back(l);
    }
    vector<int>res(m+5);
    res[0] = 1;
    vector<int>val(m+5);
    for(int t = 1; t<=m+1; t++){
        SegTree seg(m+5);
        for(int i = 0; i<=m; i++){
            seg.modify(i,res[i]);
        }
        vi res2(m+5);
        for(int i = 0; i<=m+1; i++){
            res2[i] = seg.query(0,i);
            for(int l : adj[i]){
                seg.modify(0,l,2);
            }
        }
        val[t-1] = res2[m+1];
        res = res2;
    }
    vector<int>dp(m+5);
    for(int i = 0; i<=m; i++){
        for(int j = i; j<=m; j++){
            int mult = 1;
            if(j%2 != i%2)mult = -1;
            dp[i] += val[j] * choose(j,i) * mult; dp[i] = fix(dp[i]);
        }
    }
    for(int i = m-1; i>=0; i--){
        cout << dp[i] << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果