题目描述

难度分:$865$

输入$n(1 \leq n \leq 3000)$和两个长为$n$的数组$a$和$b$，元素范围在$[0,3000]$，且均为递增数组（允许有相同元素）。

构造递增数组$c$（允许有相同元素），满足$a[i] \leq c[i] \leq b[i]$。

输出你能构造多少个不同的$c$，由于答案可能较大，对其模$998244353$后输出。

输入样例$1$

2
1 1
2 3

输出样例$1$

5

输入样例$2$

3
2 2 2
2 2 2

输出样例$2$

1

输入样例$3$

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

输出样例$3$

978222082

算法

动态规划

这种计数类题目一般要么是纯数学题，要么就是DP，或者两者的结合。

状态定义

$dp[i][cur]$表示第$i$个数为$cur$时，能够得到的方案数。显然，答案就是$\Sigma_{val=0}^{3000}dp[n][val]$。

状态转移

第$i$个数$cur$的范围应该是$[max(a[i],last),b[i]]$，状态转移方程为

$dp[i][cur]=\Sigma_{last=0}^{3000}dp[i-1][last]$，$cur \in [max(a[i],last),b[i]]$

其中$last$是上一个数$c[i-1]$，如果双重循环枚举$last$和$cur$，时间复杂度会达到$O(n^3)$，在$n \leq 3000$的数据规模下会超时。因此，可以先计算一下$dp[i-1]$的前缀和数组$s$，然后进行$O(1)$的状态转移。

$dp[i][cur]=\Sigma_{x=0}^{cur}dp[i-1][x]=s[cur]$，$cur \in [a[i],b[i]]$

复杂度分析

时间复杂度

外层循环$i$时间复杂度为$O(n)$，内层分别循环$last$（计算前缀和）和$cur$（状态转移）时间复杂度为$O(n)$，算法整体的时间复杂度为$O(n^2)$。

空间复杂度

空间瓶颈在于DP数组，状态数量为$O(n^2)$级别，因此额外空间复杂度为$O(n^2)$（也可以滚动数组优化到$O(n)$）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010, MOD = 998244353;
int n, a[N], b[N], s[N], dp[N][N];

int windowSum(int l, int r) {
    if(l > r) return 0;
    return (s[r] - (l? s[l - 1]: 0) + MOD) % MOD;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    memset(dp, 0, sizeof dp);
    for(int i = a[1]; i <= b[1]; i++) {
        dp[1][i] = 1;
    }
    for(int i = 2; i <= n; i++) {
        for(int last = 0; last <= 3000; last++) {
            s[last] = ((last? s[last - 1]: 0) + dp[i - 1][last]) % MOD;
        }
        for(int cur = a[i]; cur <= b[i]; cur++) {
            dp[i][cur] = (dp[i][cur] + windowSum(0, cur)) % MOD;
        }
    }
    int ans = 0;
    for(int i = 0; i <= 3000; i++) {
        ans = (ans + dp[n][i]) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}