[LMXOI Round 1] Random
题目背景
LMX 给 HQZ 一个有趣的序列,HQZ 为了了解 LMX 的爱好,想要解决下面的问题。
题目描述
给出一个初始全为 $0$ 长为 $n$ 的序列,我们会进行如下操作 $q$ 次。
+ 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。
也就是说我们一共会有 $(nk)^q$ 种不同的询问序列,而对于每一种不同的询问序列,对应的也就拥有了 $(nk)^q$ 个结果序列。
接着,给出一个长度为 $m$ 匹配序列 $B$,需要求出这个匹配序列在每一个结果序列中出现的次数和。注意,一个结果序列中若出现多个匹配序列应当重复计算。
由于答案太大,你只需要输出答案对 $998244353$ 取模后的结果。
**本题使用特定方式生成输入数据。**
生成格式如下: $x_i=(a \times i+b)\bmod k +1$ ,其中 $x_i$ 表示序列 $B$ 第 $i$ 位所需求的数字。
输入输出格式
输入格式
第一行四个整数 $n,m,q,k$ 其中 $m$ 为 $B$ 序列的长度。
第二行二个整数 $a,b$。
输出格式
一行一个整数表示答案。
输入输出样例
输入样例 #1
3 2 2 2
1 1
输出样例 #1
4
输入样例 #2
2 1 2 2
1 1
输出样例 #2
12
输入样例 #3
10 3 114 51419
19 2
输出样例 #3
266405589
说明
**样例解释 #1**
下述操作序列,存在序列 $B$:
+ $[1,1],[2,2]$ 序列为 $[1,2,0]$
+ $[2,2],[1,1]$ 序列为 $[1,2,0]$
+ $[2,1],[3,2]$ 序列为 $[0,1,2]$
+ $[3,2],[2,1]$ 序列为 $[0,1,2]$
对于 $100\%$ 的数据,保证 $\forall x_i \in B, 1\le x_i\le k$,$0 \le a,b\le 10^9$,且 $m\le n$。
| 子任务编号 | $n,q,k$ | $m$ | 特殊性质 | 分值 |
| :--------: | :------------------: | :----------: | :------: | :----: |
| Subtask #1 | $\le 10^9$ | $\le 200$ | $q< m$ | $5$ |
| Subtask #2 | $\le 4$ | $\le 4$ | 无 | $10$ |
| Subtask #3 | $\le 500$ | $\le 200$ | 无 | $10$ |
| Subtask #4 | $\le 2\times 10^5$ | $\le 200$ | 无 | $20$ |
| Subtask #5 | $\le 10^9$ | $\le 200$ | 无 | $20$ |
| Subtask #6 | $\le 10^9$ | $\le 3\times 10^6$ | 无 | $35$ |