Submission #16890146

---

Source Code Expand

#include <bits/stdc++.h>

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long int
#define MAX 1e9
#define MIN -1e9
#define mod 998244353
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define output(x) cout << ( x ? "Yes" : "No" ) << '\n' ;
#define mxn 100005
using namespace std;

void solve(){
    int n,k;
    cin >> n >> k;
    int l[k],r[k];
    for(int i = 0; i < k; i++){
        cin >> l[i] >> r[i];
    }
    int dp[n + 5] = {};
    int pref[n + 5] = {};
    dp[1] = 1;
    pref[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 0; j < k; j++){
            if(i <= l[j])
                continue;

            int left = l[j];
            int right = min(r[j], i - 1);
            int val = (pref[i - left] - pref[i- right - 1] + mod) % mod;
            
            dp[i] = (dp[i] + val ) % mod;
        }
        pref[i] = (pref[i - 1] % mod + dp[i] % mod) % mod;
    }
    cout << dp[n] ;
}

int32_t main()
{
    FLASH
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Submission Info

Judge Result