F.小苯的糖果游戏
Link:Nowcoder
题目描述
小苯和格格正在玩一款名为“吃糖果”的游戏，游戏的过程是这样的：
两人面前有 $n$ 堆糖果，从左到右编号从 1 到 $n$，其中第 $i$ 堆糖果中有 $a_i$ 颗糖果。初始时小苯在 0 号位置（第一堆糖果的左侧），格格在 $n+1$ 号位置。（第 $n$ 堆糖果的右侧）
假设小苯目前位于 $i$ 号糖果堆的位置，格格位于 $j$ 号糖果堆（$i < j-1$），则每秒钟都会发生如下过程：
- 如果 $i = j - 1$（即两人已经相邻），则游戏结束。
- 否则，两人轮流操作，小苯先手：
- 轮到小苯时，小苯可以选择待在原地；或跳跃到 $i+1$ 号糖果堆，然后选择吃掉所有 $a_{i+1}$ 颗糖果，或者不吃。
- 轮到格格时，格格可以选择待在原地；或跳跃到 $j-1$ 号糖果堆，然后选择吃掉所有 $a_{j-1}$ 颗糖果，或者不吃。
（当然，吃掉某堆糖果的前提是此堆糖果之前没被吃掉。换句话说每堆糖果被任何人吃掉后都会消失。）
现在我们考虑所有结束的游戏，为了公平起见，小苯希望自己和格格吃掉的糖果数量相同，他想知道有多少种不同的游戏过程能满足他的要求，请你帮他算一算吧。
（游戏过程的不同性在下方备注处给出了定义。）
输入描述:
本题含有多组测试数据。 第一行一个正整数 $T\ (1 \leq T \leq 100)$，表示测试数据的组数。 接下来对于每组测试数据，输入包含两行。 第一行一个正整数 $n\ (1 \leq n \leq 100)$，表示糖果的总堆数。 第二行 $n$ 个正整数 $a_i\ (1 \leq a_i \leq 100)$，表示每堆糖果的总个数。
输出描述:
对于每组测试数据，输出一行一个整数，表示不同的游戏过程数。 （由于结果可能很大，因此你只要输出答案对 $998244353$ 取模的值即可。）
示例1
输入
1
2
3
2 3 1 2 1 6 1 3 1 1 2 1
输出
1
2
3
6 41
提示
说明 考虑第一组测试数据，最终结束时满足小苯要求的，不同的游戏过程有：
小苯位于 $i=0$，格格位于 $j=1$，两人都没有吃糖果。
小苯位于 $i=1$，格格位于 $j=2$，两人都没有吃糖果。
小苯位于 $i=2$，格格位于 $j=3$，两人都没有吃糖果。
小苯位于 $i=3$，格格位于 $j=4$，两人都没有吃糖果。
小苯位于 $i=1$，格格位于 $j=2$，小苯选择吃掉的糖果编号集合为：${1}$，格格选择吃掉的糖果编号集合为 ${3}$。
小苯位于 $i=2$，格格位于 $j=3$，小苯选择吃掉的糖果编号集合为：${1}$，格格选择吃掉的糖果编号集合为 ${3}$。
备注: 考虑两个游戏过程：
游戏过程 1： 结束时，小苯位于 $pos_1$，小苯选择拿走的糖果堆的编号集合为 $S_1$，格格选择拿走的糖果堆编号集合为 $S_2$。
游戏过程 2： 结束时，小苯位于 $pos_2$，格格位于 $pos_2$，小苯选择拿走的糖果堆的编号集合为 $S_3$，格格选择拿走的糖果堆编号集合为 $S_4$。
定义两个游戏过程相同，当且仅当：$pos_1=pos_2$，同时 $S_1=S_3$ 且 $S_2=S4$。
否则两个游戏过程不相同。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int N = 1e2 + 5;
const int NN = 1e4 + 5;
const int M = 998244353;
int a[N], f1[N][NN], f2[N][NN];
void solve()
{
int n; cin >> n;
int s = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s += a[i];
}
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
f1[0][0] = 1;
for (int i = 1; i <= n; i++)
{// 遍历堆
for (int j = 0; j <= s; j++)
{
f1[i][j] = f1[i - 1][j]; // 不选第 i 堆糖果
if (j >= a[i])
{
f1[i][j] = (f1[i][j] + f1[i - 1][j - a[i]]) % M;
}
}
}
// f2为后缀dp
f2[n + 1][0] = 1;
for (int i = n; i >= 1; i--)
{
for (int j = 0; j <= s; j++)
{
f2[i][j] = f2[i + 1][j];
if (j >= a[i])
{
f2[i][j] = (f2[i][j] + f2[i + 1][j - a[i]]) % M;
}
}
}
int ans = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= s; j++)
{
ans = (ans + f1[i][j] * f2[i + 1][j] % M) % M;
}
}
cout << ans << endl;
}
其实我们是能够将$f2$的优化为滚动数组的，因为我们在算答案的时候只需要知道当前层的信息即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
f2[0] = 1; // 注意此处数组底标的意义
for (int i = n; i >= 1; i--)
{
for (int j = s; j >= a[i]; j--)
{
f2[j] = (f2[j] + f2[j - a[i]]) % M;
}
for (int j = 0; j <= s; j++)
{
ans = (ans + f1[i - 1][j] * f2[j] % M) % M;
}
}
ans = (ans + f1[n][0]) % M; // 一定要加上这一行，上面的循环是没有处理格格在原地的情况的，实际上就是 +1