Counting Is Fun (Easy Version)

题意

一个长度为$m$的数组b成为是good的，当且仅当通过执行下面这个操作若干次可以让数组b中所有元素变成$0$：

• 选择两个不同的下标$l$和$r$，其中$(1\le l<r\le m)$，然后$b_i(l\le i\le r)$所有元素减$1$

给定n，k，p，n为数组长度，k为数组中每个元素的取值范围为$[0,k]$，p为模数，求在$(k+1{)}^n$个数组里有多少个数组是good的

分析

首先观察到$l$是不能等于$r$的，即一次操作最少有两个元素进行减1，所以差分数组就需要选择一对$(i,j)$，其中$(i+2\le j)$，令原数组为$a$，差分数组为$b$，一次操作也就是找到一对$(i,j)$，$b_i-1$，$b_j+1$，要让所有元素都为0，差分数组所有元素也得是0，所以充要条件就是，$b_i+{\sum }_{j=1}^{i-2}{b}_j\ge 0\iff a_i-a_{i-1}+a_{i-2}\ge 0$，若某个时刻$b_i<0$而$b_1...b_{i-2}>0$一定是不合法的。

那么就可以用设计dp状态统计方案数了，根据数据范围，最大可以到$n^3$，设$d{p}_{i,j,k}$为到第$i$个为止，$a_{i-1}=j$，$a_i=k$时符合条件的方案数，转移就是$d{p}_{i,j,k}\leftarrow (d{p}_{i,j,k}+d{p}_{i-1,l,j})\%p$，其中$a_{i-2}=l,k\ge max(0,j-l)$，由此可以发现枚举$i,j,k$就已经时$n^3$级别，再考虑优化转移，发现可以考虑后缀和使得转移可以$O(1)$进行，因为转移的时候考虑的都是$k\ge max(0,j-l)$的部分

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int dp1[410][410][410], dp2[410][410][410];
void Solve() {
    int n, k, mod;
    cin >> n >> k >> mod;
    dp1[0][0][0] = 1;
    for (int i = 0; i <= k; i++) {
        dp2[0][i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int l = 0; l <= k; l++) {
                if (i == 1) {
                    for (int ll = 0; ll <= k; ll++) {
                        dp1[i][j][l] = (dp1[i - 1][ll][j] + dp1[i][j][l]) % mod;
                    }
                } else {
                    dp1[i][j][l] = (dp1[i][j][l] + dp2[i - 1][max(0, j - l)][j]) % mod;
                }
            }
        }
        for (int j = k; j >= 0; j--) {
            for (int l = 0; l <= k; l++) {
                dp2[i][j][l] = dp1[i][j][l];
                if (j + 1 <= k) {
                    dp2[i][j][l] = (dp2[i][j][l] + dp2[i][j + 1][l]) % mod;
                }
            }
        }
    }
    LL ans = 0;
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= i; j++) {
            ans = (ans + dp1[n][i][j]) % mod;
        }
    }
    cout << ans << '\n';
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int l = 0; l <= k; l++) {
                dp1[i][j][l] = dp2[i][j][l] = 0;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return 0;
}