Rockdu's Blog

Constraints

• 1≤N,K≤300
• 2≤M≤109
• N, K 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

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;
}