AGC024E

kkio · 2022-10-23 21:19:37 · 题解

如果在一个位置插入一个数，那么之后的字典序更大的要求，是插入位置之后第一个 s_i \neq s_{i+1} 的位置满足 s_i > s_{i+1} 。将连续的一段相同去重，那么每次插入的条件应该是 s_i > s_{i+1} ，当然，你放开头也可以。只要我们从小到大放，那就一定能满足条件。

设置 dp_{i,j,k} 表示长度为 i ，现在考虑放 j ，后面还有 k 个位置(不包括开头)没被决定放的方案数。

那么有转移：

初始状态 dp_{1,0,1} = 1 。答案就是 dp_{n,k,0} 。

#include <bits/stdc++.h>
using namespace std;
const int maxn=305;
int n,k,mod;
int dp[maxn][maxn][maxn];
int main()
{
    scanf("%d%d%d",&n,&k,&mod);
    dp[0][1][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=k;j++)
            for(int l=n;l>=0;l--)
                if(dp[i][j][l])
                {
                    if(l==0)
                        dp[i][j+1][i]=(dp[i][j+1][i]+dp[i][j][l])%mod;
                    else 
                        dp[i][j][l-1]=(dp[i][j][l-1]+dp[i][j][l])%mod;
                    dp[i+1][j][l]=(dp[i+1][j][l]+1ll*dp[i][j][l]*(l+1)%mod)%mod;
                }
    printf("%d",dp[n][k][0]);
}