fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 998244353;
  8.  
  9. void solve() {
  10.     int n, m;
  11.     if (!(cin >> n >> m)) return;
  12.  
  13.     // limit[i] will store the rightmost 'l' for all constraints ending at or before 'i'.
  14.     vector<int> limit(n + 1, 0);
  15.     for (int i = 0; i < m; ++i) {
  16.         int l, r;
  17.         cin >> l >> r;
  18.         limit[r] = max(limit[r], l);
  19.     }
  20.  
  21.     // Propagate the limit constraints. If a block ending at i-1 requires j >= L,
  22.     // a block ending at i (which encompasses constraints ending <= i-1) must also satisfy that.
  23.     for (int i = 1; i <= n; ++i) {
  24.         limit[i] = max(limit[i], limit[i - 1]);
  25.     }
  26.  
  27.     // dp[i] = number of valid sequences of length i ending with a block boundary at i
  28.     // sum_dp[i] = prefix sum of dp array
  29.     vector<int> dp(n + 1, 0);
  30.     vector<int> sum_dp(n + 1, 0);
  31.  
  32.     dp[0] = 1;
  33.     sum_dp[0] = 1;
  34.  
  35.     for (int i = 1; i <= n; ++i) {
  36.         // The previous block must have ended at some index j.
  37.         // The current block is s[j+1 ... i].
  38.         // For this block to be valid, it must not fully contain any forbidden constraint.
  39.         // This implies j must be >= limit[i].
  40.         // Also obviously j < i (j max is i-1).
  41.  
  42.         int l = limit[i];
  43.         int r = i - 1;
  44.  
  45.         if (l <= r) {
  46.             // Calculate sum(dp[l] ... dp[r])
  47.             int current_sum = sum_dp[r];
  48.             int prev_sum = (l > 0) ? sum_dp[l - 1] : 0;
  49.             dp[i] = (current_sum - prev_sum + MOD) % MOD;
  50.         } else {
  51.             dp[i] = 0;
  52.         }
  53.  
  54.         sum_dp[i] = (sum_dp[i - 1] + dp[i]) % MOD;
  55.     }
  56.  
  57.     // Multiply by 2 because the sequence can start with either '0' or '1'
  58.     cout << (2LL * dp[n]) % MOD << "\n";
  59. }
  60.  
  61. int main() {
  62.     // Optimize I/O operations
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(NULL);
  65.  
  66.     int t;
  67.     if (cin >> t) {
  68.         while (t--) {
  69.             solve();
  70.         }
  71.     }
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3
4 3
1 2
2 3
3 4
4 2
1 2
3 4
200 1
13 37
stdout
copy 
2
4
570529459
https://ideone.com/R3amHh
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!