fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MOD = 998244353;
  9. const int MAX_VAL = 3001; // Ci 的值最大為 3000,所以 DP 狀態的第二維需要到 3001 (索引 0 到 3000)
  10.  
  11. int main() {
  12. ios_base::sync_with_stdio(false);
  13. cin.tie(NULL);
  14.  
  15. int n;
  16. cin >> n;
  17.  
  18. vector<int> a(n);
  19. vector<int> b(n);
  20.  
  21. for (int i = 0; i < n; ++i) {
  22. cin >> a[i];
  23. }
  24. for (int i = 0; i < n; ++i) {
  25. cin >> b[i];
  26. }
  27.  
  28. // dp[i][j]: 表示考慮序列 C 的前 i+1 個元素 (C_0, ..., C_i),且 C_i = j 的合法序列數量。
  29. // 這裡使用 0-based 索引,所以 i 從 0 到 N-1
  30. vector<vector<int>> dp(n, vector<int>(MAX_VAL, 0));
  31.  
  32. // 基底 (i = 0, 對應序列 C 的第一個元素 C_0)
  33. // C_0 可以取 A[0] 到 B[0] 之間的值
  34. for (int j = a[0]; j <= b[0]; ++j) {
  35. dp[0][j] = 1;
  36. }
  37.  
  38. // 迭代計算 (i 從 1 到 N-1, 對應序列 C 的第 2 到 N 個元素)
  39. for (int i = 1; i < n; ++i) {
  40. // 計算前一層 dp[i-1] 的前綴和
  41. vector<int> prefix_sum(MAX_VAL, 0);
  42. prefix_sum[0] = dp[i - 1][0];
  43. for (int j = 1; j < MAX_VAL; ++j) {
  44. prefix_sum[j] = (prefix_sum[j - 1] + dp[i - 1][j]) % MOD;
  45. }
  46.  
  47. // 計算當前層 dp[i]
  48. // 當前元素 C_i 可以取 A[i] 到 B[i] 之間的值 j
  49. for (int j = a[i]; j <= b[i]; ++j) {
  50. // C_{i-1} 的值 k 必須滿足 A[i-1] <= k <= B[i-1] 且 k <= C_i = j
  51. // 所以 k 的範圍是 [A[i-1], min(B[i-1], j)]
  52.  
  53. int upper_bound_prev = min(b[i - 1], j);
  54. int lower_bound_prev = a[i - 1];
  55.  
  56. long long count_prev = 0;
  57. if (lower_bound_prev <= upper_bound_prev) {
  58. // 使用前綴和計算 dp[i-1] 在範圍 [lower_bound_prev, upper_bound_prev] 的和
  59. long long sum_up_to_upper = prefix_sum[upper_bound_prev];
  60. long long sum_up_to_lower_minus_1 = 0;
  61. if (lower_bound_prev > 0) {
  62. sum_up_to_lower_minus_1 = prefix_sum[lower_bound_prev - 1];
  63. }
  64.  
  65. count_prev = (sum_up_to_upper - sum_up_to_lower_minus_1 + MOD) % MOD; // 處理負數結果
  66. } else {
  67. // 這個範圍不可能有 C_{i-1} 的值,數量為 0
  68. count_prev = 0;
  69. }
  70.  
  71. dp[i][j] = count_prev;
  72. }
  73. }
  74.  
  75. // 計算最終答案
  76. // 最終答案是考慮到 C_{N-1} 時,所有可能的 C_{N-1} 值 (A[N-1] 到 B[N-1]) 對應的合法序列數量總和
  77. long long final_answer = 0;
  78. for (int j = a[n - 1]; j <= b[n - 1]; ++j) {
  79. final_answer = (final_answer + dp[n - 1][j]) % MOD;
  80. }
  81.  
  82. cout << final_answer << endl;
  83.  
  84. return 0;
  85. }
Success #stdin #stdout 0.01s 5296KB
stdin
3
1 2
2 3
3 1
stdout
0