官方题解

题目大意

给定两个非递减数组 $a,b$ 满足 $a_i\leq b_i$ ，求非递减数组 $c$ 满足 $a_i\leq c_i\leq b_i$ 的个数，并对 $998244353$ 取模。

解题思路

考虑 $DP$。

状态表示：令 $f_{i,j}$ 表示在数组 $c$ 的前 $i$ 个中且 $a_i\leq c_i \leq j$ 的数量。
状态计算：显然，$f_{i,j}$​ 一定包含 $f_{i,j−1}$​ 和 $f_{i−1,j}$​。所以转移方程如下（注意：$j$ 需要满足 $j\leq b_{i−1}$​）：

$$\begin{cases} f_{i,j}=f_{i,j-1}+f_{i-1,j} & \text{ if } j\leq b_{i-1}\\ f_{i,j}=f_{i,j-1}+f_{i-1,b_{j-1}} & \text{ if } j>b_{i-1} \end{cases}$$

在递推之前先处理一下 $i=1$ 的状态，即递推起点。

最终结果为 $f_{n,b_n}$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3010;
const int mod = 998244353;

int a[N],b[N];
ll dp[N][N];   // 前 i 个数, 第 i 个数选小于 j 的方案数

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=a[1];i<=b[1];i++) dp[1][i]=i-a[1]+1;
    for(int i=2;i<=n;i++){
        for(int j=a[i];j<=b[i];j++){
            dp[i][j]=(dp[i][j]+dp[i-1][min(b[i-1],j)])%mod;
            if(j>0) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
        }
    }
    cout<<dp[n][b[n]]<<endl;
    return 0;
}