题目描述

难度分:$787$

输入$n$，$m(1 \leq n,m \leq 50)$，$k(n \leq k \leq n \times m)$。

输出有多少个数组$a$满足$1 \leq a[i] \leq m$且$\Sigma_{i=1}^{n}a_i \leq k$。

由于结果可能非常大，对其模上$998244353$。

输入样例$1$

2 3 4

输出样例$1$

6

输入样例$2$

31 41 592

输出样例$2$

798416518

算法

记忆化搜索

状态定义

$dp[i][su]$前$i-1$个元素的和为$su$时，考虑构造子数组$[i,n]$最终可以得到的合法方案数。显然，答案就是$dp[1][0]$。

状态转移

对于当前元素，可以在$num \in [1,m]$的范围内进行枚举，状态转移方程为

$dp[i][su]=\Sigma_{num=1}^{m}dp[i+1][su+num]$

当$i \gt n$时，如果$su \leq k$，就形成了一种合法的方案。

复杂度分析

时间复杂度

$i$的取值范围是$[1,n]$，$su$的取值范围是$[1,nm]$，因此状态数量为$n^2m$。而状态转移的时间复杂度为$O(m)$，因此整体的时间复杂度为$O(n^2m^2)$。

空间复杂度

额外空间复杂度就是$dp$数组的消耗，为状态的数量，即$O(n^2m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 55, MOD = 998244353;
int n, m, k, a[N], f[N][N*N];

int dfs(int i, int su) {
    if(i > n) return su <= k? 1: 0;
    int& v = f[i][su];
    if(v != -1) return v;
    int cnt = 0;
    for(int num = 1; num <= m; num++) {
        cnt = (cnt + dfs(i + 1, su + num)) % MOD;
    }
    return v = cnt;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, 0));
    return 0;
}