#2044. 生活在对角线下

    ID: 2044 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest764来源:qoj.ac数据:公开样例快速幂

生活在对角线下

生活在对角线下

题目描述

标题: 生活在对角线下 - Problem - QOJ.ac

#4922. 生活在对角线下

Statistics

题目描述

一句话题意:

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

∑x=0n∑y=0min(x,m)(x+yx)(n−x+m−yn−x)F(x,y)

对 998244353 取模的结果。

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

输入格式

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

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

第一行两个整数 n 和 m, 保证满足 m−n=c 。

接下来 p+1 行每行 q+1 个数,第 i 行第 j 个数表示 F(x,y) 中 xi−1yj−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≤T≤105,−105≤c≤105,1≤L≤105,0≤(p+1)×(q+1)≤10。保证输入的多项式的系数属于 [0,998244353) 。

subtask 1 (1 pts):T=1,L≤103

subtask 2 (9 pts):L≤103

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 0 1 1 5
1 1 
1 1
1 1
2 2
1 2
3 4
12
278