結果

問題 No.2336 Do you like typical problems?
ユーザー momoyuumomoyuu
提出日時 2023-06-02 22:40:57
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,666 ms / 2,000 ms
コード長 5,683 bytes
コンパイル時間 3,796 ms
コンパイル使用メモリ 270,356 KB
実行使用メモリ 42,496 KB
最終ジャッジ日時 2024-06-09 00:23:46
合計ジャッジ時間 15,148 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
7,620 KB
testcase_01 AC 45 ms
7,552 KB
testcase_02 AC 43 ms
7,424 KB
testcase_03 AC 45 ms
7,552 KB
testcase_04 AC 45 ms
7,620 KB
testcase_05 AC 44 ms
7,680 KB
testcase_06 AC 44 ms
7,552 KB
testcase_07 AC 44 ms
7,552 KB
testcase_08 AC 52 ms
7,936 KB
testcase_09 AC 51 ms
7,876 KB
testcase_10 AC 51 ms
7,872 KB
testcase_11 AC 51 ms
7,936 KB
testcase_12 AC 52 ms
7,880 KB
testcase_13 AC 1,666 ms
42,344 KB
testcase_14 AC 1,616 ms
42,368 KB
testcase_15 AC 1,631 ms
42,376 KB
testcase_16 AC 1,625 ms
42,372 KB
testcase_17 AC 1,617 ms
42,496 KB
testcase_18 AC 217 ms
14,724 KB
testcase_19 AC 271 ms
14,672 KB
testcase_20 AC 847 ms
42,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 998'244'353;
//const ll mod = 1'000'000'007;
//const ll mod = 67'280'421'310'721;
struct mint{
    long long x;
    mint(long long x=0):x((x%mod+mod)%mod){}
    mint operator-() const{
        return mint(-x);
    }
    mint& operator+=(const mint& a){
        if((x+=a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator-=(const mint& a){
        if((x+=mod-a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator*=(const  mint& a){
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const{
        mint res(*this);
        return res*=a;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        mint a = *this, r = 1;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint inv() const{
        return pow(mod-2);
    }
    mint& operator/=(const mint& a){
        return (*this)*=a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
    bool operator==(const mint& a) const {
        return x == a.x;
    }
    bool operator<(const mint& a) const{
        return x < a.x;
    }
};

template< typename T1, typename T2 = T1 >
struct lazysegtree{
    using F1 = function<T1(T1,T1)>;
    using F2 = function<T2(T2,T2)>;
    using F3 = function<T1(T2,T1)>;
    //using FF = function<T1(T2,T1,int,int)>;
    int n;
    F1 f1;
    F2 f2;
    F3 f3;
    T1 e1;
    T2 e2,e3;
    vector<T1> data;
    vector<T2> lazy;//莨晄成繝・・繧ｿ
    vector<int> p;//莨晄成縺ｮ繝輔Λ繧ｰW
    /*
     * n:鬆らせ謨ｰ
     * f1:隕∫ｴ蜷悟｣ｫ縺ｮ貍皮ｮ・f2:菴懃畑邏蜷悟｣ｫ,f3:菴懃畑
     * e:蜊倅ｽ榊・
     */
    lazysegtree(int _n,F1 f1,F2 f2,F3 f3,T1 e1,T2 e2,T2 e3):f1(f1),f2(f2),f3(f3),e1(e1),e2(e2),e3(e3){
        n = 1;
        while(n<_n) n<<=1;
        data.assign(2*n,e1);
        lazy.assign(2*n,e3);
        p.assign(2*n,0);
    }

    void set(int i,T1 x){
        data[i+n-1] = x;
    }


    void build(){
        for(int i = n - 2;i>=0;i--){
            data[i] = f1(data[2*i+1],data[2*i+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            p[ni] = 1;
            lazy[ni] = f2(x,lazy[ni]);
            update(ni,l,r);
        }else{
            rangeupdate(x,a,b,2*ni+1,l,(l+r)/2);
            rangeupdate(x,a,b,2*ni+2,(l+r)/2,r);
            if(l+1<r) data[ni] = f1(data[2*ni+1],data[2*ni+2]);
        }
    }

    void rangeupdate(T2 x,int a,int b){
        rangeupdate(x,a,b,0,0,n);
    }

    void update(int ni,int l,int r){
        if(!p[ni])return;
        p[ni] = 0;
        data[ni] = f3(lazy[ni],data[ni]);
        //data[ni] = f3(lazy[ni],data[ni],l,r);
        if(l+1<r){
            p[2*ni+1] = 1;
            p[2*ni+2] = 1;
            lazy[2*ni+1] = f2(lazy[ni],lazy[2*ni+1]);
            lazy[2*ni+2] = f2(lazy[ni],lazy[2*ni+2]);
        }
        lazy[ni] = e3;
    }

    T1 query(int a,int b,int ni,int l,int r){
        update(ni,l,r);
        if(b<=l||r<=a) return e1;
        if(a<=l&&r<=b) return data[ni];
        else return f1(query(a,b,2*ni+1,l,(l+r)/2),query(a,b,2*ni+2,(r+l)/2,r));
    }

    T1 query(int a,int b){
        return query(a,b,0,0,n);
    }

    T1 operator[](const int i) const {
        return data[i+n-1];
    }
};

using dat = pair<mint,mint>;
dat cmp(dat a,dat b){
    a.first += b.first;
    a.second += b.second;
    return a;
}

dat c1(mint a,dat b){
    b.first += a * b.second;
    return b;
}

mint cc(mint a,mint b){
    return a + b;
}

mint fac[2<<17],ifac[2<<17];
int main(){
    fac[0] = 1;
    for(int i = 1;i<2<<17;i++) fac[i] = fac[i-1] * mint(i);
    for(int i = 0;i<2<<17;i++) ifac[i] = fac[i].inv();
    int n;
    cin>>n;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    vector<ll> b(n),c(n);
    for(int i = 0;i<n;i++) cin>>b[i]>>c[i];
    vector<ll> d;
    for(int i = 0;i<n;i++){
        d.push_back(b[i]);
        d.push_back(c[i]+1);
    }
    sort(d.begin(),d.end());
    d.erase(unique(d.begin(),d.end()),d.end());
    int m = d.size();
    lazysegtree<dat,mint> seg(m,cmp,cc,c1,make_pair(mint(0),mint(0)),mint(0),mint(0));
    for(int i = 0;i<m-1;i++){
        seg.set(i,make_pair(mint(0),mint(d[i+1]-d[i])));
    }
    seg.build();
    for(int i = 0;i<n;i++){
        int ni = lower_bound(d.begin(),d.end(),b[i]) - d.begin();
        int nj = lower_bound(d.begin(),d.end(),c[i]+1) - d.begin();
        seg.rangeupdate(mint(c[i]-b[i]+1).inv(),ni,nj);
    }
    mint ans = mint(n) * mint(n-1) * mint(2).inv();
    mint tmp = 0;
    for(int i = 0;i<n;i++){
        ans *= mint(c[i]-b[i]+1);
    }
    
    for(int i = 0;i<n;i++){
        int ni = lower_bound(d.begin(),d.end(),b[i]) - d.begin();
        int nj = lower_bound(d.begin(),d.end(),c[i]+1) - d.begin();
        tmp += (seg.query(ni,nj).first-mint(1)) * mint(c[i]-b[i]+1).inv();
    }
    for(int i = 0;i<n;i++){
        tmp *= mint(c[i]-b[i]+1);
    }
    tmp *= mint(2).inv();
    //cout<<tmp<<endl;
    ans -= tmp;
    for(int i = 0;i<n;i++){
        ans *= mint(c[i]-b[i]+1).inv();
    }
    //cout<<ans<<endl;
    ans *= fac[n]*fac[2].inv();
    cout<<ans<<endl;

}
0