题目大意
给定两个非递减数组 a,ba,ba,b 满足 ai≤bia_i\leq b_iai ≤bi ，求非递减数组 ccc 满足 ai≤ci≤bia_i\leq c_i\leq b_iai ≤ci ≤bi 的个数，并对 998244353998244353998244353 取模。
解题思路
考虑 DPDPDP。
状态表示：令 fi,jf_{i,j}fi,j 表示在数组 ccc 的前 iii 个中且 ai≤ci≤ja_i\leq c_i \leq jai ≤ci ≤j 的数量。
状态计算：显然，fi,jf_{i,j}fi,j 一定包含 fi,j−1f_{i,j−1}fi,j−1 和 fi−1,jf_{i−1,j}fi−1,j 。所以转移方程如下（注意：jjj 需要满足 j≤bi−1j\leq b_{i−1}j≤bi−1 ）：
{fi,j=fi,j−1+fi−1,j if j≤bi−1fi,j=fi,j−1+fi−1,bj−1 if j>bi−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} {fi,j =fi,j−1 +fi−1,j fi,j =fi,j−1 +fi−1,bj−1 if j≤bi−1 if j>bi−1
在递推之前先处理一下 i=1i=1i=1 的状态，即递推起点。
最终结果为 fn,bnf_{n,b_n}fn,bn 。
参考代码
