算法
(前缀和优化DP) $O(NM)$
记 dp[i][j]
表示考察到 $C_i$ 时,$C_i = j$ 的合法方案数
转移方程:
$ dp[i][j] = \begin{cases} \sum\limits_{k \leqslant j} dp[i - 1][k], & a[i] \leqslant j \leqslant b[i] \\\ 0, & \text{其他} \end{cases} $
此时状态数为 $O(NM)$,转移数为 $O(M)$,所以总的时间复杂度为 $O(NM^2)$,显然会超时
下面考虑优化:
对于 $\sum\limits_{k \leqslant j} dp[i - 1][k]$ 这部分可以用前缀和来加速
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> b[i];
const int M = 3001;
vector<mint> dp(M);
dp[0] = 1;
rep(i, n) {
vector<mint> p(M);
swap(dp, p);
rep(j, M - 1) p[j + 1] += p[j];
rep(j, M) {
if (a[i] <= j and j <= b[i]) {
dp[j] += p[j];
}
}
}
mint ans;
rep(i, M) ans += dp[i];
cout << ans.val() << '\n';
return 0;
}