codeforce每日一题
题目链接
题目分数:1500
题目描述
输入 $n, m(1≤n,m≤2000) k(0≤k≤n-1)$。
$n$ 块砖排成一排,把每块砖涂成 $m$ 种颜色中的一种,要求恰好有 $k$ 块砖的颜色与其左边相邻砖的颜色不同(当然,第一块砖不能在这 $k$ 块砖内)。
输出涂色方案数,模 $998244353$。
样例
输入样例1
3 3 0
输出样例1
3
输入样例2
3 2 1
输出样例2
4
算法
$(dp)$ $O(n^2)$
$f[i][j]$表示前$i$块砖,有$j$块砖与左边相邻砖颜色不同的方案数,如果当前砖的颜色与左边相邻砖的颜色相同,$f[i][j] = (f[i][j] + f[i - 1][j]) % mod$;如果当前砖颜色与左边相邻砖的颜色不同,$f[i][j] = (f[i - 1][j - 1] * (m - 1) + f[i][j]) % mod$。初始化$f[1][0] = m$。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e3 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;
int n, m, k;
LL f[N][N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m>>k;
f[1][0] = m;
rep(i, 1, n)
{
rep(j, 0, k)
{
if(i < j) break;
else{
f[i][j] = (f[i - 1][j] + f[i][j]) % mod;
if(j > 0) f[i][j] = (f[i - 1][j - 1] * (m - 1) % mod + f[i][j]) % mod;
}
}
}
cout<<f[n][k]<<endl;
return 0;
}