Colorful Bricks-codeforce 1081C
Colorful Bricks
给定n个点,排列成一排,m种颜色和k,k代表有k个点与其左边相邻的点的颜色是不同的。
求有多少种染色方案,答案可能很大,请对998244353取模。
一开始题意理解错了,以为剩下的n – k个点的颜色可以相同也可以不同,实际上要求是都要相同的,这样排列组合公式和动态规划方程都简单了许多.
排列组合
对于n个点,第一个点必须是不属于k的那个点,因为它左边没有点了.那么就有了第一个因数m
在剩下的n-1个点中选择k个,也就是第二个因数\binom{n-1}{k}
这k个点每个点可以选择的颜色数是m-1,那么第三个因数就是(m-1) ^{k}
最后答案就是m * \binom{n-1}{k} * (m-1) ^{k}
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MOD = 998244353;
ll n, m, k;
ll C[20000];
ll square( ll x ) { return x * x % MOD; }
ll fast_expt_and_mod( ll b, ll n, ll mod )
{
if ( n == 0 ) return 1;
else if ( n % 2 == 0 ) return square( fast_expt_and_mod( b, n >> 1, mod ) % mod ) % mod;
return b * fast_expt_and_mod( b, n - 1, mod ) % mod;
}
ll get_C( ll up, ll down )
{
C[0] = 1;
for ( ll i = 1; i <= down; i ++ ) C[i] = C[i-1] * i % MOD;
return C[down] *
fast_expt_and_mod(C[up], MOD - 2, MOD) % MOD *
fast_expt_and_mod(C[down-up], MOD - 2, MOD) % MOD;
}
int main()
{
scanf("%lld %lld %lld", &n, &m, &k);
ll c = get_C(k, n-1);
printf("%lld\n", (fast_expt_and_mod(m - 1, k, MOD) * c % MOD ) * m % MOD );
return 0;
}
动态规划
属于k的点有k个, 不属于k的点有n-k个
res[i][j]为当属于k的点达到i,不属于k的点达到j时的涂色方案总数
一个新的点可以通过增加一个属于k的点或者增加一个不属于k的点到达,增加属于k的点就要乘上&m-1&,根据这个写出状态转移方程
res[i][j] = res[i-1][j] * ( m – 1 ) + res[i][j-1]
其中的边界是res[0][i] = m , i \in [1, n – k]
答案是res[k][n-k]
res[0][1] = m;
for ( ll i = 1; i <= n - k; i ++ ) res[0][i] = m;
for ( ll i = 1; i <= k; i ++ )
{
for ( ll j = 1; j <= n - k; j ++ )
{
res[i][j] = (res[i-1][j] * ( m - 1 ) % MOD + res[i][j-1]) % MOD;
}
}