安吉-开营测试 T4 - Jerry's blog

原题呈现

题目描述#

香风智乃想画一幅画．这幅画一共有 $n$ 个像素，每个像素上可以画 $m$ 种颜色的其中一种．但是，如果某一种颜色连续重复出现太多次，那么就会显得这幅画很单调．具体来说，智乃不希望第 $i$ 种颜色连续出现超过 $a_i$ 次．智乃想知道，她一共能画出多少种不同的画．两幅画不同，当且仅当某个像素上所画的颜色不同．

输入格式#

从文件 draw.in 中读入数据．第一行输入两个整数 $n, m$ ．第二行输入 $m$ 个整数，第 $i$ 个表示 $a_i$ ．

输出格式#

输出到文件 draw.out 中．输出一个非负整数，表示答案对 998244353 取模后的值．

样例输入#

样例输出#

1
21

数据范围#

对于 $10\%$ 的数据， $1 \leq n, m \leq 5$ ．对于 $30\%$ 的数据， $1 \leq n, m \leq 50$ ．对于 $50\%$ 的数据， $1 \leq n, m \leq 500$ ．对于 $70\%$ 的数据， $1 \leq n, m \leq 5000$ ．对于 $100\%$ 的数据， $1 \leq a_i \leq n \leq 5000, 1 \leq m \leq 10^5$ ．

观察 $n$ 的范围，显然使用 dp．

定义状态：dp[i][j] 表示考虑前 i 个像素，最后一个颜色为 j 的方案数．

一般情况下，对于一个序列，该序列的下一个像素都可以取 $m$ 种颜色，但是有一个例外．由于不能连续重复出现太多次这一限制的存在，存在一种危险序列，满足以下所有条件：

该序列的后面 $a_k$ 个都是颜色 $k$ ．
该序列的第倒数 $a_k+1$ 个像素的颜色不是颜色 $k$ ．

此时，这个序列的下一个像素就不能是颜色 $k$ ．

若定义前 $i$ 个像素的合法方案数为 $s_i$ （无最后一个颜色的限制），合法但是后面不能再增加颜色 $j$ 的方案数为 $d_{i,j}$ ，可以预处理出 $s_i$ ，通过容斥，先计算出无视这一限制后的方案数 $s_{i - 1}$ （直接往所有合法序列后面添加颜色 $j$ ），再减去上述的不合法方案数 $d_{i - 1}$ ，就是 dp[i][j]

s_i = \sum_{j=1}^{m} dp[i][j]

d_{i,j} = s_{i-a_j} - dp[i-a_j][j]

故 dp[i][j] 的表达式为：

s_{i-1} - (s_{i-a_j-1}-dp[i-a_j-1][j])

最终结果为 s[n]．

这种方法的时间复杂度为 $O(mn)$ ．

观察到颜色种类很多，但是限制种类很少，说明有多种颜色的限制相同．那么这些颜色就可以一起处理．

修改状态：dp[i][j] 表示考虑前 i 个像素，最后一个颜色是限制为 j 的某一种颜色的方案数．

定义 cnt[i] 表示限制为 $i$ 的颜色数量．

由此，我们修改 $s_i$ 和 $d_i$ 的表达式：

s_i = \sum_{k\in a} dp[i][k] \times cnt[k]

d_i = s_{i-k} - dp[i-k][k]

dp[i][k] = s_{i-1} - (s_{i-k-1}-dp[i-k-1][k])

这样的时间复杂度为 $O(n^2+m)$ ．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int M = 1e5 + 100;
4
const int N = 5005;
5
const int MOD = 998244353;
6
int n, m;
7
map<int, int> cnt;
8
int dp[N][N], s[N];
9
int main() {
10
    cin >> n >> m;
11
    for (int i = 1; i <= m; i++) {
12
        int a;
13
        cin >> a;
14
        cnt[a]++;
15
    }
16
    vector<int> keys;
17
    for (auto i : cnt) {
18
        if (i.second != 0)
19
            keys.push_back(i.first);
20
    }
21
    s[0] = 1;
22
    for (int i = 1; i <= n; i++) {
23
        for (int j = 0; j < keys.size(); j++) {
24
            int k = keys[j];
25
            if (i - k <= 0) {
26
                dp[i][k] = s[i - 1];
27
            } else
28
                dp[i][k] = (0ll + s[i - 1] - (s[i - k - 1] - dp[i - k - 1][k]) + MOD) % MOD;
29
        }
30
        for (int j = 0; j < keys.size(); j++) {
31
            int k = keys[j];
32
            (s[i] += 1ll * dp[i][k] * cnt[k] % MOD) %= MOD;
33
        }
34
    }
35
    cout << s[n];
36
}

实际上，若一个 dp 状态与之前的连续的一段状态（开头为位置 $p$ ）都有关，则可能可以从状态 $p-1$ 进行转移．

音乐

音乐