#M087. 万能欧几里德

    ID: 4423 传统题 2000ms 512MiB 尝试: 21 已通过: 9 难度: 9 上传者: 标签>CF2800省选/NOI-类欧几里得算法幺半群区间聚合快速幂矩阵乘法

万能欧几里德

题目描述

给定非负整数 P,Q,R,L,NP,Q,R,L,N 和两个 N×NN\times N 矩阵 A,BA,B,其中 P,Q,L,NP,Q,L,N 均不为 00。求矩阵

$$C=\sum_{x=1}^{L} A^x B^{\left\lfloor\frac{Px+R}{Q}\right\rfloor}.$$

矩阵乘法的顺序为先 AxA^x、后 B⌊(Px+R)/Q⌋B^{\lfloor(Px+R)/Q\rfloor};不能交换二者。所有输出元素对 998244353998244353 取模。

本可读题面依据原始题面 PDF逐项人工转录并核对;原始 PDF 保留供查阅。

输入格式

第一行五个空格隔开的非负整数 P,Q,R,L,NP,Q,R,L,N,其中 P,Q,L,NP,Q,L,N 均不为 00。

接下来 NN 行,每行 NN 个空格隔开的非负整数,其中第 ii 行第 jj 个数表示 Ai,jA_{i,j}。

再接下来 NN 行,每行 NN 个空格隔开的非负整数,其中第 ii 行第 jj 个数表示 Bi,jB_{i,j}。

输出格式

共 NN 行,每行 NN 个空格隔开的非负整数。其中第 ii 行第 jj 个数表示答案矩阵元素 Ci,jC_{i,j} 对 998244353998244353 取模后的值。

样例

8 5 2 3 1
1
2
44

样例一可核对求和端点及向下取整:A=1,B=2A=1,B=2,对应指数为 2,3,52,3,5,所以答案为 22+23+25=442^2+2^3+2^5=44。

998244353 654321321 1234567 512 2
123 345
101 233
765 234
606 723
359941153 675459034
50358289 228823864

数据范围

  • 对于 10%10\% 的数据,L≤106L\le 10^6,N=1N=1,A1,1=1A_{1,1}=1,R=0R=0。
  • 对于 40%40\% 的数据,L≤1018L\le 10^{18},N=1N=1,A1,1=1A_{1,1}=1,R=0R=0。
  • 对于 60%60\% 的数据,L≤1018L\le 10^{18},N=1N=1,A1,1=1A_{1,1}=1。
  • 对于 80%80\% 的数据,L≤1018L\le 10^{18},N≤20N\le 20,且 AA 是单位矩阵。
  • 对于 100%100\% 的数据,L≤1018L\le 10^{18},N≤20N\le 20。
  • 对于 100%100\% 的数据,$P,Q,R,\left\lfloor\frac{PL}{Q}\right\rfloor\le 10^{18}$,0≤Ai,j,Bi,j<9982443530\le A_{i,j},B_{i,j}<998244353。

原题标注时间限制为 3s3\mathrm{s},内存限制为 512MiB512\mathrm{MiB}。