Jesselrj's Blog

CF1943D1 - Counting Is Fun (Easy Version)

题意：定义好数组为：一个由$m$个非负整数组成的数组$b$中，若$b$中所有元素可以通过以下操作使其为$0$。选择一个区间$(l, r)(1\le l< r\le m), \forall{i}, \ i\in(l, r),b_i$减去$1$。询问长度为$n$的数组，每个元素最大为$k$时，好数组个数。

可以证明，一个三元组$(a, b, c)$，当$a+c\ge b$时可以将其减为$0$。

于是设$dp[i][a][b]$为前i个数，第i-1个是a，第i个是b时的方案数。那么转移方程则为$dp[i][b][c] = \sum\limits_{a=b-c}^{k}{dp[i-1][a][b]}$。

对于求和用前缀和维护则可做到$O(n^3)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 410;

void work() {
    int n, k, p;
    cin >> n >> k >> p;
    vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n + 2; i++) { // n + 2, 0, 0 will be the ans.
        vector<vector<int>> sum(k + 1, vector<int>(k + 1, 0));
        for (int b = 0; b <= k; b++) {
            sum[b][0] = dp[0][b];
            for (int a = 1; a <= k; a++)
                sum[b][a] = (dp[a][b] + sum[b][a - 1]) % p;
        }
        for (int b = 0; b <= k; b++) {
            for (int c = 0; c <= k; c++) {
                if (b - c > 0) dp[b][c] = (sum[b][k] - sum[b][b - c - 1] + p) % p; // a > b - c is ok
                else dp[b][c] = sum[b][k]; // any a is ok
            }
        }
    }
    cout << dp[0][0] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}