Codeforces 1000D - Yet Another Problem on Subsequence

Author Avatar
Jimmy Zhang Jul 10, 2018
  • Read this article on other devices

题面

如果一个由整数组成的数组 a1,a2,,aka_1, a_2, \dots, a_k,满足 a1=k1a_1 = k - 1 并且 a1>0a_1 > 0,我们称其为好数组。而如果一个由整数组成的序列可以被划分为多个好数组,我们称这个序列是好序列。现在给你一个序列,试问有多少个好子序列,结果对 998244353 取余。

题目链接

动态规划!

首先我们不难观察到,好序列实际上就是由若干个好数组拼接得到的。

我们记 dp[i]dp[i] 代表对于后缀序列 ai,ai+1,,aka_i, a_{i + 1}, \dots, a_k 的前缀序列(也就是所有以 aia_i 开头的子序列)的答案之和。

如果 a[i]0a[i] \le 0,显然 dp[i]=0dp[i] = 0

否则,我们枚举可以拼接下一个好序列的位置 jj。位置 jj 开头的好数组有 dp[j]dp[j] 种。而在 iijj 之间除去已被确定的第 ii 位和第 jj 位,还有 ji1j - i - 1 位尚未被确定。根据好数组的定义,我们知道从 ii 开始的好数组的长度为 a[i]+1a[i] + 1,除去已被确定的开头,还有 a[i]a[i] 位尚未被确定。由于子序列并不要求连续,所以我们在这 ji1j - i - 1 位种取出 a[i]a[i] 位共有 (ji1a[i])\binom{j - i - 1}{a[i]} 种取法。另外由此我们不难得知 jj 的取值范围即 i+a[i]+1jki + a[i] + 1\le j \le k

根据乘法原理,我们不难写出状态转移方程:
dp[i]=j=i+a[i]+1k(ji1a[i])dp[j]dp[i] = \sum\limits_{j = i + a[i] + 1}^{k} \binom{j - i - 1}{a[i]} \cdot dp[j]

显然,在具体实现的时候循环要倒着写。

另外,我们需要初始化 dp[k+1]dp[k + 1]11。这等于是我们对于每一个序列虚拟了一个第 k+1k + 1 位,以应对整个序列就是一个好数组的情况(比如样例一)。

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/07/10/codeforces-1000d/