#P51969. 「THUPC 2019」摆家具 / furniture

「THUPC 2019」摆家具 / furniture

题目描述

你有 kk 件不同的家具,需要摆放在 nn 个不同的房间中。假设每个房间足够大,并且只考虑每件家具处于哪个房间(而不考虑房间内部如何摆放),那么总共有 nkn^k 种不同的摆放方式(注意,不是 knk^n)。

摆放家具也算一门学问了,至少不太好乱摆的吧?对于每种摆放方式,我们可以给这种方式打分。例如,某个方案把餐桌放到了卫生间,或是一个卧室放了两张床而另一个卧室没有床,就会获得比较低的分数。由于这个分数关于每件家具、每个房间不是独立的,我们会输入所有 nkn^k 种摆放方式的分数。

你现在心血来潮,想换一换房间的布局。给出一种初始时的摆放方式,你会重复 TT 次下述操作:每次,你会任选一件家具,然后将这件家具移动到任意一个其他房间中。每一轮有 k(n1)k(n-1) 种决策(选择家具的方案数乘以选择另一个房间的方案数),所以总共有 kT(n1)Tk^T(n-1)^T 种决策。你需要计算这每一种决策后的摆放方式的得分之和。

不仅如此,我们会给出 qq 次询问,每次输入初始时的摆放方式与 TT,你需要在线地回答 kT(n1)Tk^T(n-1)^T 种决策后的得分之和(取模)。详见输入与输出格式。

我们如下定义一种摆放方式的编号:

我们将家具用 0 到 k1k-1 的不同整数编号,房间用 00n1n-1 的不同整数编号。设在某种摆放方式下,第 ii 号家具被放在了 pip_i 号房间中,则定义这种摆放方式的编号为 i=0k1pini\sum_{i=0}^{k-1} p_i n^i。可以发现,所有的 nkn^k 种摆放方式的编号恰好是 00nk1n^k -1 的不同整数。

另外,设 P=998244353P=998244353

输入格式

第一行输入三个正整数 n,k,qn, k, q

接下来 nkn^k 行,每行输入一个小于 PP 的正整数,依次表示编号为 0,1,,nk10, 1, \dots, n^k - 1 的摆放方式的得分。

接下来 qq 行,每行输入两个非负整数。设某行的输入为 a,ba, b(保证 0a<nk,0b<P0 \leq a < n^k, 0 \leq b < P),则此次询问的初始摆放方式的编号为 aa,而 T=brmodPT=b \cdot r \bmod P,其中 rr 是你上一个输出的数(对于第一次询问为 11)。

同一行内输入的相邻两个数之间以一个空格隔开。

保证 n2n \geq 2k1k \geq 1nk106n^k \leq 10^6q5×105q \leq 5 \times 10^5

输出格式

对于每次询问输出一行,包含一个非负整数,表示该询问的得分之和对 PP 取模的结果。

样例

2 3 3
1
10
100
1000
998244245
100000
1000000
10000000
0 1
0 1
1 233
2
2202003
444957911

第一次询问中,初始摆放方式的编号为 00T=1T=1

初始时,00 号家具放在 00 号房间,11 号家具放在 00 号房间,22 号家具放在 00 号房间。经过 11 次操作后,可能的情况有:

  • 00 号家具移动到 11 号房间,此后的摆放方式编号为 11,得分为 1010
  • 11 号家具移动到 11 号房间,此后的摆放方式编号为 22,得分为 100100
  • 22 号家具移动到 11 号房间,此后的摆放方式编号为 44,得分为 998244245998244245

所以,所有情况的总得分为 998244355998244355,对 PP 取模后为 22

第二次询问中,初始摆放方式的编号为 00T=2T=2

初始时,00 号家具放在 00 号房间,11 号家具放在 00 号房间,22 号家具放在 00 号房间。经过 22 次操作后,可能的情况有:

  • 00 号家具移动到 11 号房间,然后将 00 号家具移动到 00 号房间,此后的摆放方式编号为 00,得分为 11
  • 00 号家具移动到 11 号房间,然后将 11 号家具移动到 11 号房间,此后的摆放方式编号为 33,得分为 10001000
  • 00 号家具移动到 11 号房间,然后将 22 号家具移动到 11 号房间,此后的摆放方式编号为 55,得分为 100000100000
  • 11 号家具移动到 11 号房间,然后将 00 号家具移动到 11 号房间,此后的摆放方式编号为 33,得分为 10001000
  • 11 号家具移动到 11 号房间,然后将 11 号家具移动到 00 号房间,此后的摆放方式编号为 00,得分为 11
  • 11 号家具移动到 11 号房间,然后将 22 号家具移动到 11 号房间,此后的摆放方式编号为 66,得分为 10000001000000
  • 22 号家具移动到 11 号房间,然后将 00 号家具移动到 11 号房间,此后的摆放方式编号为 55,得分为 100000100000
  • 22 号家具移动到 11 号房间,然后将 11 号家具移动到 11 号房间,此后的摆放方式编号为 66,得分为 10000001000000
  • 22 号家具移动到 11 号房间,然后将 22 号家具移动到 00 号房间,此后的摆放方式编号为 00,得分为 11

所以,所有情况的总得分为 22020032202003,对 PP 取模后为 22020032202003

第三次询问中,初始摆放方式的编号为 11T=513066699T=513066699。初始时,00 号家具放在 11 号房间,11 号家具放在 00 号房间,22 号家具放在 00 号房间。

……(省略至少 35130666993^{513066699} 行)

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。