AT_past202309_o.数列の足し算

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ ，以及一个长度为 $K$ 的序列 $P = (P_1, P_2, \ldots, P_K)$ 。

现需要对序列 $A$ 执行 $Q$ 次操作。

第 $q$ $q$ 次操作 $(1 \leq q \leq Q)$ $(1 \leq q \leq Q)$ 给出整数 $l_q, r_q\ (1 \leq l_q \leq r_q \leq N)$ $l_{q}, r_{q} (1 \leq l_{q} \leq r_{q} \leq N)$ ，以及一个长度为 $K$ $K$ 的序列 $b_q = (b_{q,1}, b_{q,2}, \ldots, b_{q,K})$ $b_{q} = (b_{q, 1}, b_{q, 2}, \dots, b_{q, K})$ 。对于第 $q$ $q$ 次操作，构造一个无限长的序列 $B = (B_1, B_2, \ldots)$ $B = (B_{1}, B_{2}, \dots)$ ，满足如下线性递推关系：
- $B_j = b_{q,j}\ (1 \leq j \leq K)$
- $B_j = P_1 B_{j-1} + P_2 B_{j-2} + \ldots + P_K B_{j-K}\ (j > K)$

然后对于每个 $i=1,2,\ldots,r_q-l_q+1$ ，令 $A_{l_q+i-1} \gets A_{l_q+i-1} + B_i$ 。

请你输出所有操作结束后， $A$ 序列中的每一个元素对 $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}$

输出格式

输出所有操作执行完后 $A$ 的每个元素对 $998244353$ 取模后的值。

输入输出样例

输入#1

输出#1

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

说明/提示

样例解释 1

初始时， $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 = (3, 6, 9, 12, 6)$ 。

数据范围

$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$
所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页