QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
[+6]

# 4922. 生活在对角线下

Statistics

题目描述

一句话题意:

给定一个 p×q 次的二元多项式 F(x,y),求

\sum_{x = 0}^n \sum_{y = 0}^{\min(x, m)} \binom{x + y}{x} \binom{n - x + m - y}{n - x} F(x, y)

998244353 取模的结果。

每个测试点有 T 组询问,保证所有询问中 m - n 的值是一个常数 c

输入格式

第一行输入五个整数 T, c, p, q, N,分别表示询问数量,m - n = c,二元多项式的次数以及此测试点询问中 n的上限,即保证此测试点中所有询问满足 n \leq N

接下来输入 T 组测试数据,每组测试数据输入方式如下:

第一行两个整数 nm保证满足 m - n = c

接下来 p + 1 行每行 q + 1 个数,第 i 行第 j 个数表示 F(x, y)x^{i - 1} y^{j - 1} 的系数。

输出格式

输出 T 行,每行一个整数表示题目中所求的答案。

样例数据

input

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

output

12
278

数据范围

为了方便,以下记 L = \max(N, N + c) ,即询问中坐标的范围。

对于所有测试数据:1 \leq T \leq 10^5, -10^5 \leq c \leq 10^5, 1 \leq L \leq 10^5, 0 \leq (p + 1) \times (q + 1) \leq 10。保证输入的多项式的系数属于 [0, 998244353)

subtask 1 (1 pts):T = 1, L \leq 10^3

subtask 2 (9 pts):L \leq 10^3

subtask 3 (20 pts):T = 1, p = q = 0

subtask 4 (20 pts):p = q = 0

subtask 5 (20 pts):T = 1

subtask 6 (10 pts):c = 0

subtask 7 (20 pts):没有特殊限制。

时间限制:1.5s

空间限制:512MB