跳舞
这是一道比 zjp 的 T1 还签到的签到题.
题目描述
了解蛮勇的人都知道, 蛮勇是一个喜欢跳舞的男孩子.
最近蛮勇迷上了一套叫 hop 的舞蹈. 舞蹈一共有k个动作, 分为m种. 为了方便, 我们用数字1...m表示每种动作.
蛮勇想在 hop 的基础上自己创作舞蹈. 他每次会随机做出一个1...m内的动作, 如果做完某个动作后,最近连续的 k 个动作恰好和标准 hop 相吻合, 那么就会获得 1 个积分. 积分从 0 开始,每出现一次就增加 1 分,重叠出现也分别计分;达到 p 分时立即停止舞蹈。
现在蛮勇想问你, 对于i=1...n, 如果要刚好在第i个动作后停止, 有多少种跳舞的方案.
输入格式
第一行是 4 个整数n,m,k,p. 第二行是k个数si, 表示 hop 的动作序列.(si∈[1,m])
输出格式
n 行每行一个整数, 表示答案对 998244353 取模的结果.
样例输入
6 2 3 2
1 2 1
样例输出
0
0
0
0
1
3
Sample Explanation
长度为 5 的合法序列有: {1,2,1,2,1} 长度为 6 的合法序列有: {1,2,1,1,2,1}, {1,1,2,1,2,1}, {2,1,2,1,2,1}
数据范围
所有数据满足 1≤n,k,p,m≤105,1≤si≤m。
| 子任务 |
分值 |
附加限制 |
| 1 |
10 |
n≤20,m≤2 |
| 2 |
n≤1000,p=1 |
| 3 |
n≤1000,p=2 |
| 4 |
n≤100000,m=1 |
| 5 |
n≤100000,p=1 |
| 6 |
n≤100000,p=2 |
| 7 |
40 |
无特殊限制 |