#P10374. [2021年联测]傅里叶与矩阵

    ID: 9492 传统题 7000ms 888MiB 尝试: 9 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-生成函数求系数部分分式分解乘积树多点求值多项式求逆多项式牛顿迭代多项式除法NTT批量求逆快速幂费马小定理

[2021年联测]傅里叶与矩阵

题目描述

有一个 mm 行 nn 列的矩阵,第 ii 列所有格子的权值均为 aia_i,且 a1,…,ana_1,\ldots,a_n 两两不同。

每次询问给定行号 kk。考虑从 (1,1)(1,1) 到 (k,n)(k,n) 的所有最短路径,每步向下或向右移动一个格子。一条路径的权值是其经过的所有格子的权值之积,包含起点和终点。

求所有这些路径的权值之和对 998244353998244353 取模的结果。

输入格式

第一行三个整数 m,n,qm,n,q。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 qq 行,每行一个整数 kk。

输出格式

每次询问输出一行一个整数,表示相应答案。

样例 1

2 3 2
1 3 5
1
2
15
135

样例 2

5 2 5
1 2
1
2
3
4
5
2
6
14
30
62

样例 3

3 3 3
215 228 229
1
2
3
11225580
555879289
157593602

数据范围

  • 10%10\% 的数据满足 m,n≤2000m,n\le2000。
  • 另外 25%25\% 的数据满足 m≤105m\le10^5。
  • 另外 15%15\% 的数据满足 q≤10,n≤2000q\le10,n\le2000。
  • 另外 40%40\% 的数据满足 q=1q=1。
  • 剩下 10%10\% 的数据满足 q≤10q\le10。
  • 所有数据满足 1≤k≤m≤10181\le k\le m\le10^{18},1≤n,q≤1051\le n,q\le10^5,1≤ai<9982443531\le a_i<998244353,且所有 aia_i 两两不同。

原 PDF 题面