自动搬运

查看原文

来自洛谷，原作者为

	SfumatoCannon_ 你谷最菜蓝钩（AFOed）

搬运于2025-08-24 22:33:24，当前版本为作者最后更新于2021-08-19 11:58:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

0.吐槽

赛事想出来的做法，当时觉得这题挺简单的（倒是代码实现上调了好久）

比完赛一看题解，？？怎么个个都这么复杂，又是压维又是滚动数组的（甚至让我一度怀疑数据过水）

下面，我就介绍一种做法，理解起来很自然，优化起来也很容易。

1.题意解释

有一个长度为 $n$ 的序列，其中包含的数字范围为从 $1$ 到 $m$.

规定数字 $i$ 最多只能连续出现 $a_i$ 次。

求满足上述要求的序列一共有多少中，答案对 $10^9+7$ 取模。

2.解题思路

我们发现，这道题目的核心在于 “规定数字 $i$ 最多只能连续出现 $a_i$ 次” 这个限制条件。

我们不妨思考一下：如果我们按照线性动态规划的方式，一个一个地往表格里填数字，当我填到第 $i$ 个数字的时候，和它关系最大的是什么？没错，是第 $i-1$ 个数字。

如果第 $i-1$ 个数字和第 $i$ 个数字不一样的话，那么第 $i$ 个数字填下去，一定是合法的。

否则呢？设当时填的数字为 $j$ ，如果第 $i-1$ 个数字和第 $i$ 个数字是一样的，且 $a_j> i-1$ 的话，我们仍然可以放心大胆地填下去，因为填下去之后，连续出现的数字是不可能超过 $a_j$ 个的（因为本身就只有 $a_j$ 个数字啊）。

那么，如果第 $i-1$ 个数字和第 $i$ 个数字是一样的，且 $a_j\leq i-1$ 的时候呢？那么在前面 $i-1$ 个数字构成的组合里，就不可避免地会出现一种情况，它由恰好 $a_j$ 个 $j$ 结尾，当且仅当这种情况时，第 $i$ 个数字不能填成 $j$.那么，我们怎么计算这种非法情况的方案数呢？

我们知道，在这种情况下，我们要填的数是第 $i$ 个数，而且从第 $i-a_j$ 个数到第 $i-1$ 个数全部都是 $j$. 那么问题来了：第 $i-a_j-1$ 个数是几呢？没错，只要不是 $j$ 就行了！

而且我们还可以知道，这种情况下，第 $i-a_j$ 个数到第 $i-1$ 个数全都是固定死的，真正对非法方案数产生贡献的，只有前面的 $i-a_j-1$ 个数。也就是说，“填到第 $i-a_j-1$ 个数且不是以 $j$ 结尾” 的方案数总和，等于 “填到第 $i-1$ 个数，且从 $i-a_j$ 到 $i-1$ 全部都是 $j$ 的方案数”。好好思考一下上面这句话！

所以，第 $i-1$ 个数字等于第 $i$ 个数字时的合法方案总数

$=$ (前面 $i-1$ 个数字构成的合法方案总数) $-$ (从 $i-a_j$ 到 $i-1$ 全部都是 $j$ 的方案数)

$=$ (前面 $i-1$ 个数字构成的合法方案总数) $-$ (前面 $i-a_j-1$ 个数字构成的不是以 $j$ 结尾的方案数总和).

现在我们知道了第 $i-1$ 个数字不等于第 $i$ 个数字时的合法方案总数，也知道了他们相等时的合法方案总数，那么把它们加起来，就知道了我们要求的方案数。

想到了以上这些，状态转移式子就很好推了。我们设 $dp[i][j]$ 表示当前填到第 $i$ 个数，且结尾数字是 $j$ 的合法方案总数，那么必然有：

$$dp[i][j]=\sum_{k=1,k\not=j}^{m}dp[i-1][k]+(dp[i-1][j]-\sum_{k=1,k\not=j}^{m}dp[i-a[j]-1][k]) $$$$=\sum_{k=1}^{m}dp[i-1][k]-\sum_{k=1,k\not=j}^{m}dp[i-a[j]-1][k]. $$

这种做法是 $O(n^3)$ 的，拿不到满分，但我们可以很容易观察出，式子里面的 $\sum_{k=1}^{m}$ 是可以预处理出来的。

设 $sum[i]=\sum\limits_{k=1}^{m}dp[i][k]$ ,于是式子转化为：

$$dp[i][j]=sum[i-1]-(sum[i-a[j]-1]-dp[i-a[j]-1][j]). $$

转化成了 $O(n^2)$ 的，于是这道题就可做了。

至于滚动数组什么的？不需要！只要不用 long long 就可以卡过去。

另外在代码实现上，我们还需要注意之前说过的 $a_j>i-1$ 的情况，并予以特判。

还有一个地方需要特判：那就是当 $m=1$ 且唯一的 $a[1]<n$ 的时候，这种情况下是不可能填完的，应输出0。（对于其余的情况，可以证明是肯定存在解的，12121212...地填即可）

---

3.Code

#include <cstdio>
typedef long long ll;
#define MODNUM 1000000007
#define MAXN 7001
ll n, m;
unsigned int dp[MAXN][MAXN];
ll sum[MAXN];
ll a[MAXN];
int main()
{
    ll i, j, k;
    scanf("%lld%lld", &n, &m);
    for (i = 1; i <= m; i++)
        scanf("%lld", &a[i]);
    if (m == 1 && a[1] < n)
    {
        printf("0");
        return 0;
    }
    for (i = 1; i <= m; i++)
        dp[1][i] = 1;
    sum[1] = m;
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            dp[i][j] = sum[i - 1];
            if (i > a[j])
            {
                if (i == a[j] + 1)
                    dp[i][j] = (dp[i][j] - 1 + MODNUM) % MODNUM;
                else
                    dp[i][j] = (dp[i][j] - (sum[i - a[j] - 1] - dp[i - a[j] - 1][j]) + MODNUM) % MODNUM;
            }
        }
        for (j = 1; j <= m; j++)
            sum[i] = (sum[i] + dp[i][j]) % MODNUM;
    }
    printf("%lld", sum[n]);
    return 0;
}