AGC024 E - Sequence Growing Hard
? 解题记录 ? ? Atcoder ? ? 动态规划 ?    2018-07-13 22:49:19    1183    0    0

Problem Statement

Find the number of the possible tuples of sequences (A0,A1,…,AN) that satisfy all of the following conditions, modulo M:

  • For every i (0≤iN)Ai is a sequence of length i consisting of integers between 1 and K (inclusive);
  • For every i (1≤iN)Ai−1 is a subsequence of Ai, that is, there exists 1≤xii such that the removal of the xi-th element of Ai would result in a sequence equal to Ai−1;
  • For every i (1≤iN)Ai is lexicographically larger than Ai−1.

Constraints

  • 1≤N,K≤300
  • 2≤M≤109
  • NK and M are integers.


Input

Input is given from Standard Input in the following format:

N K M

Output

Print the number of the possible tuples of sequences (A0,A1,…,AN), modulo M.


Sample Input 1

Copy
2 2 100

Sample Output 1

Copy
5

Five tuples below satisfy the conditions:

  • (),(1),(1,1)
  • (),(1),(1,2)
  • (),(1),(2,1)
  • (),(2),(2,1)
  • (),(2),(2,2)


Sample Input 2

Copy
4 3 999999999

Sample Output 2

Copy
358


Sample Input 3

Copy
150 150 998244353

Sample Output 3

Copy
186248260


题意:每一次你可以把1~k之间的数拿出1个插入到数组A的任意位置,操作N次(拿出的数可重)。并且要求每一次操作后的字典序不减。问最后有多少种可能的序列。

深深的感觉到自己的DP技巧太低……对于这样的题我现有的DP技术完全不足以攻克。

这个题巧妙记录DP状态就可以规避烦人的组合数……

考虑字典序在什么时候会减小——比如说在xxxxb的这一串数中,再插入一个x,形成xxxxxb那么要求x一定比b大。并且注意到我们可以规定每一次x都放在最后面,这样我们的答案就不会算重。

有了这些后,我们记录dp[i][j][k]表示当前进行到第i个操作,放到数字j,前面有k+1个地方可以放(注意这意味着有k段连续的数字,因为开头也是可以放的)。转移如下:

  1. dp[i][j][k - 1] += dp[i][j][k] (k > 0)表示当前数不放
  2. dp[i][j + 1][i] += dp[i][j][k] (k == 0) 同样也是当前数不放的状态,但是注意到我们没位置可以放了,我们这时就需要跳到下个数。
  3. dp[i + 1][j][k] += dp[i][j][k] * (k + 1) 表示我们放置这个数,那么我们多进行了一次操作并且有k+1中选择。

代码挺短……我挺傻……

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 3e2 + 5;
 
int mod, n, k;
LL dp[maxn][maxn][maxn], ans;
 
int main() {
	scanf("%d%d%d", &n, &k, &mod);
	dp[0][1][0] = 1;
	for(register int i = 0; i <= n; ++i)
		for(register int j = 1; j <= k; ++j)
			for(register int p = i; p >= 0; --p) {
				if(p) (dp[i][j][p - 1] += dp[i][j][p]) %= mod;
				else (dp[i][j + 1][i] += dp[i][j][p]) %= mod;
				(dp[i + 1][j][p] += dp[i][j][p] * (p + 1)) %= mod;
			}
	printf("%lld", dp[n][k + 1][n]);
	return 0;
}


上一篇: AGC021 E - Ball Eat Chameleons

下一篇: Atcoder Code Festival 2017 Exhibition B - Increment and Swap

1183 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航