31. 粉刷匠

àì夳堔傛蜴生んèń 2022-04-02 08:43 188阅读 0赞

Description

龙神认为宿舍的墙上一片白不太好看，所以决定给墙涂上颜色。

龙神有种颜色的颜料(颜料中没有白色且互不相同)，分别编号为第种颜色。每一种颜色的颜料多到用不完。我们认为白色是，墙的高度不计(???)。龙神给墙涂色是很讲究的，每次只能选墙上全白的一段染色，也就是不能和已经染的颜色段有交集。同时，还要求每次染的一段只能是一些连续的整单位的墙，并且宽度不小于

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70][]

#include "stdio.h"
    long long f[2005][2];
    int main(int argc, char const *argv[])
    {
        int t;
        scanf("%d",&t);
        while(t--){
            int n, m, k;
            scanf("%d%d%d", &n, &m, &k);
            for (int i = 0; i <= n + 1; i++){
                f[i][0] = 0;
                f[i][1] = 0;
            }
            f[1][0] = 1;
            if(k == 1){
                f[1][1] = m;
            }
            else {
                f[1][1] = 0;
                f[k][1] = m;
            }
            for (int i = 2; i <= n; i++){
                if(i == k){
                    f[i][0] = (f[i - 1][0]%998244353 + f[i - 1][1]%998244353)%998244353; 
                    f[k][1] = m;
                    continue;
                }
                else{
                    f[i][0] = (f[i - 1][0]%998244353 + f[i - 1][1]%998244353)%998244353; 
                    if(i < k){
                        f[i][1] = f[i - 1][1]%998244353;
                    }
                    else{
                        f[i][1] = (f[i - 1][1]%998244353+f[i - k][0]%998244353 * m+f[i - k][1]%998244353 * (m - 1))%998244353;
                    }
                }
            }
            printf("%lld\n", (f[n][0]%998244353+f[n][1]%998244353)%998244353);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70]: /images/20220402/6afb5b0902e848969de22c8e7281eca7.png