提出 #74305408

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 998244353
#define INF 1e18
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define vi vector<int>
#define vs vector<string>
#define pii pair<int, int>
#define mii map<int, int>
#define seti set<int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define pr(a) cout<<a<<endl;
#define printList(a) for (auto &x : a) cout << x << " ";cout<<endl;
#define printMap(a) for (auto &x : a) cout << x.ff << " " << x.ss << endl;
#define PI 3.1415926535897932384626
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define w(x) int x; cin>>x; while(x--)
#define sortall(x) sort(all(x))
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vpii vector<pii>
#define matrix(n,m) vvi matrix(n, vi(m, 0));
#define printMatrix(matrix) for(auto &x:matrix){for(auto &y:x)cout<<y<<" ";cout<<endl;}
#define inputMatrix(matrix) for(auto &x:matrix)for(auto &y:x)cin>>y;
#define sortMatrix(matrix) for(auto &x:matrix)sortall(x);
#define rotateMatrix(matrix) reverse(all(matrix));for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define matrixSum(matrix) int sum=0;for(auto &x:matrix)for(auto &y:x)sum+=y;cout<<sum<<endl;
#define matrixProduct(matrix) int product=1;for(auto &x:matrix)for(auto &y:x)product*=y;cout<<product<<endl;
#define matrixMax(matrix) int mx=INT_MIN;for(auto &x:matrix)for(auto &y:x)mx=max(mx,y);cout<<mx<<endl;
#define matrixMin(matrix) int mn=INT_MAX;for(auto &x:matrix)for(auto &y:x)mn=min(mn,y);cout<<mn<<endl;
#define matrixTranspose(matrix) for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define maxEle(a) *max_element(all(a))
#define minEle(a) *min_element(all(a))
#define sumEle(a) accumulate(all(a),0)
#define productEle(a) accumulate(all(a),1,multiplies<int>())
#define maxIndex(a) max_element(all(a))-a.begin()
#define minIndex(a) min_element(all(a))-a.begin()
#define findIndex(a,x) find(all(a),x)-a.begin()
#define findEle(a,x) find(all(a),x)!=a.end()
#define countEle(a,x) count(all(a),x)
#define lowerEle(a,x) lower_bound(all(a),x)-a.begin()
#define upperEle(a,x) upper_bound(all(a),x)-a.begin()
#define gcd(a,b) __gcd(a,b)
#define hi cout<<"Hello\n";
#define yes cout<<"Yes\n";
#define no cout<<"No\n";

int Binary_exp(int a, int b, int c ){
    int ans = 1;
    while(b){
        if(b&1){
            ans =(ans*1LL*a) % c;
        }
        a = (a*1LL*a) % c;
        b/=2;
    }
    return ans;
}

int C(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; }
int modInv(int a) { return Binary_exp(a, MOD - 2, MOD); }
bool isPrime(int n){ if(n<=1)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true; }

template<class T>ostream &operator<<(ostream &os,const vector<T> &p){for(auto &it:p)os<<it<<' ';return os;}
template<class T>void dbs(string str,T t){cerr<<str<<":"<<t<<endl;}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cerr<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}

struct Seg {
    int n;
    vector<int> t, lz;

    Seg(int n) : n(n), t(4*n, 0), lz(4*n, 1) {}

    void push(int v) {
        if (lz[v] != 1) {
            for (int c : {2*v, 2*v+1}) { 
                t[c]=t[c]*lz[v]%MOD; 
                lz[c]=lz[c]*lz[v]%MOD; 
            }
            lz[v] = 1;
        }
    }

    void mul(int v, int l, int r, int ql, int qr, int x) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { 
            t[v]=t[v]*x%MOD; lz[v]=lz[v]*x%MOD; 
            return; 
        }

        push(v); int m = (l+r)/2;
        mul(2*v,l,m,ql,qr,x); 
        mul(2*v+1,m+1,r,ql,qr,x);
        t[v] = (t[2*v]+t[2*v+1])%MOD;
    }

    void add(int v, int l, int r, int p, int x) {
        if (l == r) { 
            t[v]=(t[v]+x)%MOD; 
            return; 
        }
        push(v); int m = (l+r)/2;
        if (p <= m) add(2*v,l,m,p,x); 
        else add(2*v+1,m+1,r,p,x);
        t[v] = (t[2*v]+t[2*v+1])%MOD;
    }
    
    void mul(int l, int r, int x) { 
        if (l <= r) mul(1,0,n-1,l,r,x); 
    }
    void add(int p, int x) { 
        add(1,0,n-1,p,x); 
    }
    int sum() { 
        return t[1]; 
    }
};

void solved(){
    int n, m; 
    cin >> n >> m;
    vector<vector<int>> adj(n+2);

    for (int i = 0; i < m; i++) {
        int x, y; 
        cin >> x >> y;
        adj[y].push_back(x);
    }
    Seg seg(n);
    seg.add(0, 1);
    int tot = 0, ans = 0;

    for (int i = 1; i < n; i++) {
        for (int x : adj[i+1]) {
            if (x >= 2) seg.mul(0, x-2, 2);
            tot++;
        }

        int maxi = (Binary_exp(2, tot, MOD) - seg.sum() + MOD) % MOD;
        seg.add(i, maxi);
        if (i == n-1) ans = maxi;
    }
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solved();
    }
    return 0;
}

提出情報

ジャッジ結果