A6754. 「NOI2025」序列变换

给定两个长度为 $n$ 的整数序列 $B = [b_1, \ldots, b_n]$，$C = [c_1, \ldots, c_n]$。对于长度为 $n$ 的非负整数序列 $D = [d_1, \ldots, d_n]$，设 $S(D)$ 为所有满足 $d_i = 0$ 的下标 $i$ 的集合，定义 $f(D) = \sum_{i \in S(D)} b_i$，$g(D) = \prod_{i \in S(D)} c_i$。特别地，若 $S(D)$ 为空，则 $f(D) = 0$，$g(D) = 1$。

小 L 有一个长度为 $n$ 的**正整数序列** $A = [a_1, \ldots, a_n]$。小 L 可以对序列 $A$ 做如下修改：

- 选择序列 $A$ 的两个**相邻**的下标 $i, j$（即 $1 \leq i, j \leq n$ 且 $|i - j| = 1$），若 $a_i \leq a_j$，则将 $a_j$ 改为 $a_j - a_i$，同时将 $a_i$ 改为 $0$。

小 L 可以进行任意多次修改操作，也可以不进行任何修改。对于所有序列 $A$ 通过以上修改操作可以得到的序列 $D$，小 L 想求出 $f(D)$ 的最大值以及 $g(D)$ 之和，请你帮助他求出这两个值。形式化地，记 $T(A)$ 为序列 $A$ 通过以上修改操作可以得到的**所有序列的集合**，你需要求出 $\max_{D \in T(A)} f(D)$ 以及 $\sum_{D \in T(A)} g(D)$。其中，由于 $\sum_{D \in T(A)} g(D)$ 可能较大，你只需要求出其对 $1,000,000,007$ 取模后的结果。

从文件 sequence.in 中读入数据。

**本题包含多组测试数据。**

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个正整数 $n$，表示序列长度。

第二行包含 $n$ 个正整数 $a_1, \ldots, a_n$，表示序列 $A$。

第三行包含 $n$ 个整数 $b_1, \ldots, b_n$，表示序列 $B$。

第四行包含 $n$ 个正整数 $c_1, \ldots, c_n$，表示序列 $C$。

输出到文件 sequence.out 中。

对于每组测试数据，仅输出一行，其中包含两个整数，分别表示 $\max_{D \in T(A)} f(D)$ 以及 $\sum_{D \in T(A)} g(D)$ 对 $1,000,000,007$ 取模后的结果。**注意：$\max_{D \in T(A)} f(D)$ 不需要对 $1,000,000,007$ 取模。**

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见「评分方式」。

```cpp
#include <bits/stdc++.h>
#define FL(i, a, b) for (int i = (a); i <= (b); ++i)
#define FR(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
const int N = 5e3 + 10;
const int MOD = 1e9 + 7;
const ll INFLL = 1e18;
int n, a[N], b[N], c[N], ic[N];
int pl[N], pr[N], v[N], iv[N];
ll mi[2][N][N], ct[2][N][N];
ll s[N], t[N], f[N], g[N];
int Qpow(int a, int b) {
int ret = 1;
for (; b; b >>= 1) {
if (b & 1)
ret = (ll)ret * a % MOD;
a = (ll)a * a % MOD;
}
return ret;
}
int Inv(int x) {
return Qpow(x, MOD - 2);
}
void Solve() {
scanf("%d", &n);
FL(i, 1, n) {
scanf("%d", &a[i]);
t[i] = t[i - 1] + (i & 1? -a[i] : a[i]);
}
FL(i, 1, n) {
scanf("%d", &b[i]);
s[i] = s[i - 1] + b[i];
}
v[0] = iv[0] = 1;
FL(i, 1, n) {
scanf("%d", &c[i]);
v[i] = (ll)v[i - 1] * c[i] % MOD;
ic[i] = Inv(c[i]);
iv[i] = Inv(v[i]);
}
FL(i, 1, n) {
mi[0][i][i - 1] = mi[1][i][i - 1] = INFLL;
ct[0][i][i - 1] = ct[1][i][i - 1] = 0;
FL(j, i, n) {
FL(k, 0, 1) {
mi[k][i][j] = mi[k][i][j - 1];
ct[k][i][j] = ct[k][i][j - 1];
}
mi[j & 1][i][j] = min(mi[j & 1][i][j], (ll)b[j]);
ct[j & 1][i][j] = (ct[j & 1][i][j] + ic[j]) % MOD;
}
}
FL(i, 1, n) {
int d = a[i];
FL(j, i, n) {
d = a[j + 1] - d;
if (j == n || d <= 0) {
pl[i] = j;
break;
}
}
d = a[i];
FR(j, i, 1) {
d = a[j - 1] - d;
if (j == 1 || d <= 0) {
pr[i] = (j > 1 && !d? j - 1 : j);
break;
}
}
}
fill(f, f + n + 1, -INFLL);
fill(g, g + n + 1, 0);
f[0] = 0, g[0] = 1;
FL(i, 0, n) {
FL(j, i + 1, n) {
int l = max(i + 1, pr[j]), r = min(j, pl[i + 1]);
if (l > r){
continue;
}

int h = (ll)g[i] * v[j] % MOD * iv[i] % MOD;
if (t[j] - t[i] == 0) {
f[j] = max(f[j], f[i] + (s[j] - s[i]));
g[j] = (g[j] + h) % MOD;
} else if (t[j] - t[i] > 0) {
f[j] = max(f[j], f[i] + (s[j] - s[i]) - mi[0][l][r]);
g[j] = (g[j] + (ll)h * ct[0][l][r]) % MOD;
} else {
f[j] = max(f[j], f[i] + (s[j] - s[i]) - mi[1][l][r]);
g[j] = (g[j] + (ll)h * ct[1][l][r]) % MOD;
}
}
}
printf("%lld %lld\n", f[n], g[n]);
}
int main() {
int T;
scanf("%*d %d", &T);
while (T--) {
Solve();
}
return 0;
}
```