[noi37]列队

直接统计答案，令dp[i][j]表示前i个数最长的颜色各不相同后缀长度为j的方案数，如果一直令j<m，那么就相当于统计了方案数。

如何推出dp[i][j]呢？考虑i-1的最长前缀是多少：当小于j-1或等于j时，显然无法拼接成j；当等于j-1时，第i个位置就有m-j+1种方案；当大于j时，第i个位置对于每种都仅有一种方案。

综上，即$dp[i][j]=(m-j+1)\cdot dp[i-1][j-1]+\sum_{k=j+1}^{m-1}dp[i-1][k]$，计算时间复杂度为$o(n^{3})$，用后缀和维护一下。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,m,p,ans,sum[5001],f[5001];

 4 int main(){

 5     scanf("%d%d%d",&n,&m,&p);

 6     f[0]=1;

 7     for(int i=1;i<=n;i++){

 8         for(int j=m-1;j;j--){

 9             f[j]=((m-j+1LL)*f[j-1]+sum[j])%p;

10             sum[j]=(sum[j+1]+f[j])%p;

11         }

12         f[0]=0;

13     }

14     for (int i=1;i<m;i++)ans=(ans+f[i])%p;

15     printf("%d",ans);

16 }

巴特西

[noi37]列队

最新文章

热门文章