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

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

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

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

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

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

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

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

另外,设 P=998244353

输入格式

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

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

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

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

保证 n \geq 2 k \geq 1 n^k \leq 10^6 q \leq 5 \times 10^5

输出格式

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

样例

样例输入 1
2 3 3
1
10
100
1000
998244245
100000
1000000
10000000
0 1
0 1
1 233
样例输出 1
2
2202003
444957911
样例说明 1

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

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

  • 0 号家具移动到 1 号房间,此后的摆放方式编号为 1 ,得分为 10
  • 1 号家具移动到 1 号房间,此后的摆放方式编号为 2 ,得分为 100
  • 2 号家具移动到 1 号房间,此后的摆放方式编号为 4 ,得分为 998244245

所以,所有情况的总得分为 998244355 ,对 P 取模后为 2

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

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

  • 0 号家具移动到 1 号房间,然后将 0 号家具移动到 0 号房间,此后的摆放方式编号为 0 ,得分为 1
  • 0 号家具移动到 1 号房间,然后将 1 号家具移动到 1 号房间,此后的摆放方式编号为 3 ,得分为 1000
  • 0 号家具移动到 1 号房间,然后将 2 号家具移动到 1 号房间,此后的摆放方式编号为 5 ,得分为 100000
  • 1 号家具移动到 1 号房间,然后将 0 号家具移动到 1 号房间,此后的摆放方式编号为 3 ,得分为 1000
  • 1 号家具移动到 1 号房间,然后将 1 号家具移动到 0 号房间,此后的摆放方式编号为 0 ,得分为 1
  • 1 号家具移动到 1 号房间,然后将 2 号家具移动到 1 号房间,此后的摆放方式编号为 6 ,得分为 1000000
  • 2 号家具移动到 1 号房间,然后将 0 号家具移动到 1 号房间,此后的摆放方式编号为 5 ,得分为 100000
  • 2 号家具移动到 1 号房间,然后将 1 号家具移动到 1 号房间,此后的摆放方式编号为 6 ,得分为 1000000
  • 2 号家具移动到 1 号房间,然后将 2 号家具移动到 0 号房间,此后的摆放方式编号为 0 ,得分为 1

所以,所有情况的总得分为 2202003 ,对 P 取模后为 2202003

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

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

数据范围与提示

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

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