题意概括

给定 $m$ 个完全相同的乒乓球和 $n$ 个不同的盒子。第 $i$ 个盒子最多只能放入 $a_i$ 个乒乓球。求将这 $m$ 个球全部分配到 $n$ 个盒子中的合法方案数。由于结果可能很大，输出方案数对 1000000007 取模的结果。 假设本题的数据范围为 $n, m \le 2000$，$0 \le a_i \le m$。输入的第一行为 $n$ 和 $m$，第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$。输出一个整数表示取模后的方案数。

样例分析

输入： 2 3 2 2

输出： 2

解释： 一共有 2 个盒子和 3 个乒乓球。第 1 个盒子最多放 2 个球，第 2 个盒子最多放 2 个球。 合法的分配方案有以下两种：

• 第 1 个盒子放 1 个球，第 2 个盒子放 2 个球。
• 第 1 个盒子放 2 个球，第 2 个盒子放 1 个球。 总计 2 种方案，输出 2。

题目分析

这是一个求非负整数解个数的问题，需要求满足 $x_1 + x_2 + \dots + x_n = m$ 且 $0 \le x_i \le a_i$ 的解的数量。

可以通过动态规划来求解。定义状态 $f_{i, j}$ 表示将 $j$ 个球分配到前 $i$ 个盒子中的方案数。 对于第 $i$ 个盒子，我们枚举它放入的球数 $k$，其中 $k$ 需要满足 $0 \le k \le a_i$ 且 $k \le j$。 状态转移方程为：

$$f_{i, j} = \sum_{k=0}^{\min(j, a_i)} f_{i-1, j-k}$$

按照这个方程直接计算，每次转移需要遍历 $k$，在 $n, m \le 2000$ 的情况下总计算量会达到 $O(nm^2)$，效率不足。需要对转移过程进行优化。

将上述方程展开观察，求 $f_{i, j}$ 相当于求上一层状态 $f_{i-1}$ 中一段连续区间的和。我们写出相邻状态 $f_{i, j-1}$ 的表达式：

$$f_{i, j-1} = \sum_{k=0}^{\min(j-1, a_i)} f_{i-1, j-1-k} $$

将 $f_{i, j}$ 和 $f_{i, j-1}$ 相减，抵消掉公共部分后得到：

$$f_{i, j} - f_{i, j-1} = f_{i-1, j} - f_{i-1, j-a_i-1} $$

移项后即可得到优化后的状态转移方程：

$$f_{i, j} = f_{i, j-1} + f_{i-1, j} - f_{i-1, j-a_i-1} $$

当 $j \le a_i$ 时，不存在越界项，方程简化为 $f_{i, j} = f_{i, j-1} + f_{i-1, j}$。 通过这个转化，我们将每次转移的时间复杂度从 $O(m)$ 降到了 $O(1)$。在计算过程中，注意处理取模操作中的负数情况，确保结果在 $[0, 1000000007)$ 范围内。

参考实现

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

int n, m;
int a[2005];
ll f[2005][2005];
ll md = 1000000007;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        f[i][0] = f[i-1][0];
        for(int j = 1; j <= m; ++j) {
            f[i][j] = (f[i][j-1] + f[i-1][j]) % md;
            if(j > a[i]) {
                f[i][j] = (f[i][j] - f[i-1][j - a[i] - 1] + md) % md;
            }
        }
    }
    cout << f[n][m] << "\n";
    return 0;
}

复杂度分析

时间复杂度：状态总数为 $O(nm)$，经过前缀和差分优化后，每次状态转移的时间为 $O(1)$，总时间复杂度为 $O(nm)$。 空间复杂度：使用了一个二维数组记录所有的动态规划状态，空间复杂度为 $O(nm)$。