题目描述
给定非负整数 P,Q,R,L,N 和两个 N×N 矩阵 A,B,其中 P,Q,L,N 均不为 0。求矩阵
$$C=\sum_{x=1}^{L} A^x B^{\left\lfloor\frac{Px+R}{Q}\right\rfloor}.$$
矩阵乘法的顺序为先 Ax、后 B⌊(Px+R)/Q⌋;不能交换二者。所有输出元素对 998244353 取模。
本可读题面依据原始题面 PDF逐项人工转录并核对;原始 PDF 保留供查阅。
输入格式
第一行五个空格隔开的非负整数 P,Q,R,L,N,其中 P,Q,L,N 均不为 0。
接下来 N 行,每行 N 个空格隔开的非负整数,其中第 i 行第 j 个数表示 Ai,j。
再接下来 N 行,每行 N 个空格隔开的非负整数,其中第 i 行第 j 个数表示 Bi,j。
输出格式
共 N 行,每行 N 个空格隔开的非负整数。其中第 i 行第 j 个数表示答案矩阵元素 Ci,j 对 998244353 取模后的值。
样例
8 5 2 3 1
1
2
44
样例一可核对求和端点及向下取整:A=1,B=2,对应指数为 2,3,5,所以答案为 22+23+25=44。
998244353 654321321 1234567 512 2
123 345
101 233
765 234
606 723
359941153 675459034
50358289 228823864
数据范围
- 对于 10% 的数据,L≤106,N=1,A1,1=1,R=0。
- 对于 40% 的数据,L≤1018,N=1,A1,1=1,R=0。
- 对于 60% 的数据,L≤1018,N=1,A1,1=1。
- 对于 80% 的数据,L≤1018,N≤20,且 A 是单位矩阵。
- 对于 100% 的数据,L≤1018,N≤20。
- 对于 100% 的数据,$P,Q,R,\left\lfloor\frac{PL}{Q}\right\rfloor\le 10^{18}$,0≤Ai,j,Bi,j<998244353。
原题标注时间限制为 3s,内存限制为 512MiB。