E - Removal
首先不考虑去重,可以写出以下 DP
,设 表示不去重情况下,考虑前
个数字,删除了
个,且最后一个为数字为
的方案数,有如下转移:
然后拿着这个东西取跑一遍样例,果真是错的,然后研究一下 DP
值,看看重复的都是什么情况。
这里以第一个样例为例,重复的点为去除前两个和后两个的两种情况,从 DP
转移的角度观察这个问题,当 的时候,我们考虑
和
的情况:
m = 1: 子序列为 "1" 或 "2"
m = 2: 子序列为 ""
然后到了 ,我们会从
转移出一个
"1"
,从 转移出一个
"1"
,两个就重复了。
思考归纳一下,设两个序列为 pre
和 pre+s[i + 1]
那么前一种情况加上 ,后一种情况不加,就会出现重复。
所以去重的操作就是:
int n, m, k, s[N]; mint dp[N][11][11];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> n >> m >> k) {
forn (i, 1, n) cin >> s[i];
dp[1][0][s[1]] = 1;
dp[1][1][0] = 1;
rep (i, 1, n) forn (j, 0, m) {
if (j) dp[i + 1][j][s[i + 1]] -= dp[i][j - 1][s[i + 1]];
forn (t, 0, k) {
dp[i + 1][j][s[i + 1]] += dp[i][j][t];
if (j < m) dp[i + 1][j + 1][t] += dp[i][j][t];
}
}
mint ans = 0;
forn (t, 0, k) ans += dp[n][m][t];
cout << ans.r << '\n';
forn (i, 1, n) forn (j, 0, m) forn (t, 0, k)
dp[i][j][t] = 0;
}
return 0;
}