【题解】【上海】【积木染色（二）】

解析：
    状态表示：f[i][j] 表示前 i 块积木中恰好有 j 块积木和它前面的积木颜色不同。

	状态转移：
	考虑第 i 块积木：如果和第 i−1 块颜色相同，则方案数为：f[i−1][j]
    如果和第 i−1块颜色不同，第 i 块积木可选颜色只要和前者不同即可，则有 m−1 种选择，则方案数为：
	f[i−1][j−1]∗(m−1)	因此，
	f[i][j]=f[i−1][j]+f[i−1][j−1]∗(m−1)
	注意边界问题：
	f[1][0]=m
    
    #include <bits/stdc++.h>
using namespace std;
const int N = 5010;
const int P = 1000000007;
long long f[N][N];
int main(){
	int n, m , p;
	cin >> n >> m >> p;
	f[1][0] = m;
	f[1][1] = 0;
	for(int i = 2; i <= n; i ++){
		for(int j = 0; j < i && j <= p; j ++){
			if(j == 0) f[i][j] = f[i - 1][j];
			f[i][j] = (f[i - 1][j] + (f[i - 1][j - 1] * (m - 1)) % P) % P;
		}
	}
	cout << f[n][p];
	return 0;
}