abc222D 夹在两升序数组之间的升序数组个数

给定长度为n的两升序数组A[i]和B[i]，其中A[i]<=A[i+1]，B[i]<=B[i+1]，并且0<=A[i]<=B[i]<=3000，找长度为n的数组C[i]，满足A[i]<=C[i]<=B[i]。求满足该条件的C的个数，结果对998244353取余。
1<=n<=3000

设dp[i][j]表示前i个数以j结尾的方案数，那么$ dp[i][j]=\sum_{k=0}^{j} dp[i-1][k] $，这样递推时间复杂度是O(n^3)，会TLE。观察发现这个可以用前缀和优化到O(n^2)，另外可以用滚动数组优化空间到O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

template<int MOD>
struct MInt {
    int x;
    int norm(int u) const {u%=MOD; if(u<0) u+=MOD; return u;}
    MInt(int v=0):x(norm(v)) {}
    int val() const {return x;}
    MInt operator-() const {return MInt(norm(MOD-x));}
    MInt inv() const {assert(x!=0); return power(MOD-2);}
    MInt &operator*=(const MInt &o) {x=norm(x*o.x); return *this;}
    MInt &operator+=(const MInt &o) {x=norm(x+o.x); return *this;}
    MInt &operator-=(const MInt &o) {x=norm(x-o.x); return *this;}
    MInt &operator/=(const MInt &o) {*this *= o.inv(); return *this;}
    friend MInt operator*(const MInt &a, const MInt &b) {MInt ans=a; ans*=b; return ans;}
    friend MInt operator+(const MInt &a, const MInt &b) {MInt ans=a; ans+=b; return ans;}
    friend MInt operator-(const MInt &a, const MInt &b) {MInt ans=a; ans-=b; return ans;}
    friend MInt operator/(const MInt &a, const MInt &b) {MInt ans=a; ans/=b; return ans;}
    friend std::istream &operator>>(std::istream &is, MInt &a) {int u; is>>u; a=MInt(u); return is;}
    friend std::ostream &operator<<(std::ostream &os, const MInt &a) {os<<a.val(); return os;}
    MInt power(int b) const {int r=1, t=x; while(b){if(b&1) r=r*t%MOD; t=t*t%MOD; b/=2;} return MInt(r);}
};
using mint = MInt<998244353>;

const int N = 3000;
int n, a[N+1], b[N+1];
mint dp[N+1], pre[N+1];
mint sum(int l, int r) {
    return l ? pre[r] - pre[l-1] : pre[r];
}
void solve() {
    cin >> n;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n) cin >> b[i];
    dp[0] = 1;
    partial_sum(dp, dp+1+N, pre);
    rep(i,1,n) {
        rep(j,0,N) dp[j] = 0;
        rep(j,a[i],b[i]) {
            dp[j] = sum(a[i-1], j);
        }
        partial_sum(dp, dp+1+N, pre);
    }
    cout << pre[N] << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}