← 返回题目列表

AtCoder · past202309_o

O. 添加序列

中文机器翻译题面 查看原题

问题陈述

给你一个长度序列 N, A=(A_1,A_2,\ldots,A_N),另一个长度 K, P=(P_1,P_2,\ldots,P_K).

我们现在执行以下操作 Q 对序列的操作 A.

  • 的 树的 q第次操作 (1\leq q \leq Q) 用整数表示 l_q,r_q\ (1\leq l_q \leq r_q\leq N) 和长度序列 K, b_q = (b_{q,1},b_{q,2},\ldots,b_{q,K})。 对于 q-th 操作,考虑无限序列 B=(B_1,B_2,\ldots) 由以下线性递推关系确定,并添加 B_i to A_{l_q+i-1} 对于每个 i=1,2,\ldots,r_q-l_q+1.
    • B_j=b_{q,j}\ (1\leq j \leq K)
    • B_j=P_1B_{j-1}+P_2B_{j-2}+\ldots +P_KB_{j-K}\ (j > K)

求模值 998244353,每个元素 A 完成所有操作后。

约束

  • 1\leq N,Q \leq 2\times 10^5
  • 1\leq K \leq 10
  • 1\leq l_q \leq r_q\leq N
  • 0\leq A_i,P_i,b_{q,i} < 998244353
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K Q
A_1 A_2 \ldots A_N
P_1 P_2 \ldots P_K
L_1 R_1
B_{1,1} B_{1,2} \ldots B_{1,K}
\vdots
l_Q r_Q
b_{Q,1} b_{Q,2} \ldots b_{Q,K}

输出

打印取模值 998244353,元素 A 完成所有操作后。


示例输入 1

5 2 3
0 0 0 0 0
2 1
1 4
3 1
3 5
4 1
2 2
5 9

示例输出 1

3 6 9 12 6

最初, A=(0,0,0,0,0,0).

  • 在第一次操作中, B=(3,1,5,11,27,\ldots)。经过这次操作后, A=(3,1,5,11,0,0).
  • 在第二次操作中, B=(4,1,6,13,32,\ldots)。经过这次操作后, A=(3,1,9,12,6).
  • 在第三次操作中, B=(5,9,23,55,133,\ldots)。经过这次操作后, A=(3,6,9,12,6).

因此,在所有操作之后, A is (3,6,9,12,6).


示例输入 2

1 3 1
5
1 0 1
1 1
3 1 4

示例输出 2

8

示例输入 3

10 3 5
306334866 801978559 895954374 576826717 755317213 872021310 894146017 171871727 347837426 489203653
259995927 523608184 755770553
4 7
822177140 73169010 811074390
7 8
739309938 819084714 711663615
1 9
105947194 88003242 226522376
6 8
544083472 975159386 830222368
1 9
478160947 233931690 460328037

示例输出 3

890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653