Avito Cool Challenge 2018 C. Colorful Bricks ( CF1081C )

题目：Colorful Bricks

题意：

给出3个整数 n , m , k 。分别代表有n块砖，有m种颜色，其中有k块砖和自己左边的砖颜色不一样。问有几种染色方案。

思路：

dp。

令f[i][k]表示前i块砖，有k块和左边的不一样的方案数。

边界：f[1][0]=m。

转移方程：

f[i][k]=(f[i-1][k]+(k==0?0:f[i-1][k-1])*(m-1))%md;

代码：

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 2000
#define md 998244353 
#define ll long longint n,m,K;
ll f[maxn+5][maxn+5];int main() {
    read(n),read(m),read(K);f[1][0]=m;for(int i=2;i<=n;i++) {
    for(int k=0;k<=K;k++) {
    f[i][k]=(f[i-1][k]+(k==0?0:f[i-1][k-1])*(m-1))%md;}}printf("%lld",f[n][K]);return 0;
}