#P7386. [2019雅礼集训]跳舞

    ID: 7400 传统题 2000ms 512MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-字符串KMPborder 链多项式与生成函数普通生成函数有理生成函数生成函数求系数多项式求逆多项式对数多项式指数多项式牛顿迭代NTT截断幂级数导数积分转化CF2800

[2019雅礼集训]跳舞

跳舞

这是一道比 zjp 的 T1 还签到的签到题.

题目描述

了解蛮勇的人都知道, 蛮勇是一个喜欢跳舞的男孩子.

最近蛮勇迷上了一套叫 hop 的舞蹈. 舞蹈一共有kk个动作, 分为mm种. 为了方便, 我们用数字1...m1...m表示每种动作.

蛮勇想在 hop 的基础上自己创作舞蹈. 他每次会随机做出一个1...m1...m内的动作, 如果做完某个动作后,最近连续的 kk 个动作恰好和标准 hop 相吻合, 那么就会获得 1 个积分. 积分从 00 开始,每出现一次就增加 11 分,重叠出现也分别计分;达到 pp 分时立即停止舞蹈。

现在蛮勇想问你, 对于i=1...ni=1...n, 如果要刚好在第ii个动作后停止, 有多少种跳舞的方案.

输入格式

第一行是 4 个整数n,m,k,pn,m,k,p. 第二行是kk个数sis_{i}, 表示 hop 的动作序列.(si∈[1,m]).(s_{i}\in [1,m])

输出格式

nn 行每行一个整数, 表示答案对 998244353998244353 取模的结果.

样例输入

6 2 3 2
1 2 1

样例输出

0
0
0
0
1
3

Sample Explanation

长度为 55 的合法序列有: {1,2,1,2,1}\{1,2,1,2,1\} 长度为 66 的合法序列有: {1,2,1,1,2,1}\{1,2,1,1,2,1\}, {1,1,2,1,2,1}\{1,1,2,1,2,1\}, {2,1,2,1,2,1}\{2,1,2,1,2,1\}

数据范围

所有数据满足 1≤n,k,p,m≤1051\le n,k,p,m\le10^5,1≤si≤m1\le s_i\le m。

子任务 分值 附加限制
1 10 n≤20,m≤2n\le20,m\le2
2 n≤1000,p=1n\le1000,p=1
3 n≤1000,p=2n\le1000,p=2
4 n≤100000,m=1n\le100000,m=1
5 n≤100000,p=1n\le100000,p=1
6 n≤100000,p=2n\le100000,p=2
7 40 无特殊限制