2023牛客暑期多校训练营4

J - Qu'est-ce Que C'est?

https://ac.nowcoder.com/acm/contest/57358/J

## 题解

$$t=\min\left\{\sum_{i=1}^{x}a_i,\sum_{i=2}^{x}a_i,\dots,\sum_{i=x}^{x}a_i\right\}$$

$$-t\leq a_{x+1}\leq m$$

• $dp_{i,j}:=$ 数列已经确定了 $i$ 位，且后缀和最小值为 $j$ 的情况下的方案总数。

• 如果 $j\geq0$：$dp_{i,j}$ 转移到 $dp_{i,a_{x+1}}$
• 如果 $j<0$：$dp_{i,j}$ 转移到 $dp_{i,j+a_{x+1}}$

$$a_{x+1}=\min\left\{a_{x+1}+\sum_{i=1}^{x}a_i,a_{x+1}+\sum_{i=2}^{x}a_i,\dots,a_{x+1}+\sum_{i=x}^{x}a_i,a_{x+1}\right\}$$

$$t+a_{x+1}=\min\left\{a_{x+1}+\sum_{i=1}^{x}a_i,a_{x+1}+\sum_{i=2}^{x}a_i,\dots,a_{x+1}+\sum_{i=x}^{x}a_i,a_{x+1}\right\}$$

for (int i = m; i >= -m; i--)
dp[1][i + m] = 1;
for (int i = 2; i <= n; i++) {
for (int j = m; j >= -m; j--) {
if (j >= 0) {
for (int k = m; k >= j - m; k--) {
dp[i][j + m] = (dp[i][j + m] + dp[i - 1][k + m]) % MOD;
}
} else {
for (int k = m; k >= -j; k--) {
dp[i][j + m] = (dp[i][j + m] + dp[i - 1][k + m]) % MOD;
}
}
}
}

## 代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MOD = 998244353;
constexpr int MAXN = 5050;
int n, m;
int dp[2 * MAXN], sum[2 * MAXN];

void solve()
{
cin >> n >> m;
for (int i = m; i >= -m; i--)
{
dp[i + m] = 1;
sum[i + m] = sum[i + 1 + m] + 1;
}
for (int i = 2; i <= n; i++)
{
for (int j = m; j >= -m; j--)
{
if (j >= 0)
dp[j + m] = sum[j];
else
dp[j + m] = sum[m - j];
}
for (int j = m; j >= -m; j--)
sum[j + m] = (sum[j + m + 1] + dp[j + m]) % MOD;
// for (int j = m; j >= -m; j--)
//     cout << sum[j + m] - sum[j + m + 1] << " \n"[j == -m];
}
cout << sum[0] << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}