[LMXOI Round 1] Random

Luogu

IDLGP10116

Time1000ms

Memory512MB

DifficultyP5

O2优化组合数学容斥原理

给出一个初始全为 $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$ 位所需求的数字。 ## Input 第一行四个整数 $n,m,q,k$ 其中 $m$ 为 $B$ 序列的长度。第二行二个整数 $a,b$。 ## Output 一行一个整数表示答案。 [samples] ## Background LMX 给 HQZ 一个有趣的序列，HQZ 为了了解 LMX 的爱好，想要解决下面的问题。 ## Note **样例解释 #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$ |

Samples

Input #1

3 2 2 2
1 1

Output #1

Input #2

2 1 2 2
1 1

Output #2

Input #3

10 3 114 51419
19 2

Output #3

266405589

API Response (JSON)

{
  "problem": {
    "name": "[LMXOI Round 1] Random",
    "description": {
      "content": "给出一个初始全为 $0$ 长为 $n$ 的序列，我们会进行如下操作 $q$ 次。 + 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。 也就是说我们一共会有 $(nk)^q$ 种不同的询问序列，而对于每一种不同的询问序列，对应的也就拥有了 $(nk)^q$ 个结果序列。 接着，给出一个长度为 $m$ 匹配序列 $B$，需要求出这个匹配序列在每一个结果序列",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10116"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个初始全为 $0$ 长为 $n$ 的序列，我们会进行如下操作 $q$ 次。\n\n+ 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。\n\n也就是说我们一共会有 $(nk)^q$ 种不同的询问序列，而对于每一种不同的询问序列，对应的也就拥有了 $(nk)^q$ 个结果序列。\n\n接着，给出一个长度为 $m$ 匹配序列 $B$，需要求出这个匹配序列在每一个结果序列...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments