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;
        }
    }