题目链接：http://noi.ac/contest/12/problem/37
题目:
小W收到了一张纸带，纸带上有 n个位置。现在他想把这个纸带染色，他一共有 m 种颜色，每个位置都可以染任意颜色，但是他发现如果某连续 m 个位置被染成了 m 种不同的颜色，那么就不美观，于是他决定让任意的相邻 m 个位置的颜色至少有两个位置相同。他想知道他一共有多少种染色的方案。
输入格式
第一行三个整数 n，m，p。
输出格式
输出一行一个整数，表示答案对 p 取模的结果。
题解：
我们考虑DP，设序列为{a}
dp[i][j]为考虑前i个位置，[i-j+1,i]中的颜色互不相同，并且ai-j与这段区间中的某一个位置颜色相同
我们枚举第i+1个位置和[i-j+1,i]中的哪一个颜色相同或者全部不同，进行转移
dp[i+1][j+1]=dp[i][j]*(m-j)
dp[i+1][k]+=dp[i][j](1<=k<=j)
这样的话时间复杂度是O(N^3)的
发现第二个转移可以前缀和优化一下，显然dp[i+1][k]可以从dp[i][k~(m-1)]转移而来
时间复杂度O(N^2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
typedef long long ll;
using std::min;
const int N=+;
int n,m;
ll p;
ll dp[N][N],sum[N][N];
int main()
{
scanf("%d%d%d",&n,&m,&p);
dp[][]=;
for (int i=;i<=n;i++)
{
for (int j=;j<=min(i,m-);j++)
{
(dp[i][j]+=dp[i-][j-]*(m-(j-))%p)%=p;
(dp[i][j]+=sum[i-][j])%=p;
}
for (int j=m-;j>=;j--)
{
sum[i][j]=(sum[i][j+]+dp[i][j])%p;
}
}
ll ans=;
for (int i=;i<m;i++) (ans+=dp[n][i])%=p;
printf("%lld\n",ans);
return ;
}