思路
计数要么组合数学推公式(加法原理、乘法原理、容斥原理),要么 $DP$(也是组合),本题每个 $a_i$ 都不同,大概率后者。
用 $f(i, j)$ 表示以第 $i$ 根水管结尾,且进水量之和减去出水量之和等于 $j$ 的所有区间构成的集合的元素个数,则答案等于 $\sum_{i = 1}^{n} f(i, 0)$。
这样定义状态第二维的题目还有:
对于 $f(i, j)$ 对应的所有区间,可根据是否只包含第 $i$ 根水管,以及第 $i$ 根水管是进水还是出水分 $4$ 类。
- 只包含第 $i$ 根水管。
- 若它作为进水口,若 $j == a[i]$,则 $f(i, j) = 1$,否则 $f(i, j) = 0$。
- 若它作为出水口,若 $j == -a[i]$,则 $f(i, j) = 1$,否则 $f(i, j) = 0$。
- 不只包含第 $i$ 根水管,即至少还包含第 $i - 1$ 根水管。由于整个区间进水量之和减去出水量之和为 $j$,设除了第 $i$ 根水管,前面以第 $i - 1$ 根水管结尾的区间的进水量之和减去出水量之和为 $x$,不难发现 $f(i, j) = f(i - 1, x)$,下面讨论 $x$ 具体是多少,以及等式为何成立。
- 若第 $i$ 根水管作为进水口,则 $x + a[i] = j$,即 $x = j - a[i]$,由于 $f(i - 1, j - a[i])$ 与 $f(i, j)$ 中的区间一一对应,即 $f(i - 1, j - a[i])$ 中的任意区间加上第 $i$ 根水管就是 $f(i, j)$ 中的一个区间,反之,$f(i, j)$ 中的任意区间去掉第 $i$ 根水管,就是 $f(i - 1, j - a[i])$ 中的一个区间,因此 $f(i, j) = f(i - 1, j - a[i])$。
- 若第 $i$ 根水管作为出水口,则 $x - a[i] = j$,即 $x = j + a[i]$,由于上述相同原因或根据乘法原理,对整个区间分两步考虑,第一步考虑到以 $i - 1$ 结尾,有 $f(i - 1, j + a[i])$ 种情况;第二步只有将第 $i$ 根水管包含进来这一种情况,因此 $f(i, j) = f(i - 1, j + a[i]) \times 1$。
由加法原理,$f(i, j)$ 为以上四类方案数之和。
记 $m = \sum_{i = 1}^{n} a_i \in [0, 10000]$,则 $j \in [-10000, 10000]$。由于数组下标非负,可在 $j$ 上加上偏移量 $10000$,使之落于 $[0, 20000]$。
状态数 $nm$,转移 $O(1)$,因此算法时间复杂度 $O(nm) \sim O(10^7)$,空间复杂度 $4 Bytes \times 2nm = 8 \times 10^7 Bytes < 80 MBytes$。
由于 $f(i)$ 只依赖 $f(i - 1)$,但 $j$ 的依赖有大有小,因此不能直接去掉第一维,但可以使用滚动数组。优化后的内存占用 $4 Bytes \times 2 \times 2m = 16 \times 10^4 Bytes < 160 KBytes$。
#include <iostream>
using namespace std;
const int N = 1010, M = 10010, MOD = 1e9 + 7;
int n;
int a[N], g[2][M << 1];
#define f(i, j) g[(i) & 1][(j) + M]
#define range(i, l, r) for (int i = l; i <= r; ++i)
int main() {
scanf("%d", &n);
range(i, 1, n) scanf("%d", a + i);
int res = 0;
f(0, 0) = 1;
range(i, 1, n) {
range(j, -M + 1, M - 1) {
if (abs(j) == a[i]) f(i, j) = 1;
else f(i, j) = 0;
if (i == 1) continue;
if (j - a[i] > -M)
f(i, j) = (f(i, j) + f(i - 1, j - a[i])) % MOD;
if (j + a[i] < M)
f(i, j) = (f(i, j) + f(i - 1, j + a[i])) % MOD;
}
res = (res + f(i, 0)) % MOD;
}
printf("%d\n", res);
return 0;
}
谢谢佬总结,当时没听懂