QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 1024 MB Total points: 100
[0]

# 622. 多项式多点求值

Statistics

给定多项式 F(z)=n1i=0fizim 个非负整数 x1,x2,,xm。对每个 1im 你需要计算 f(xi) 的值。

输入格式

第一行两个整数 n,m,描述多项式的次数为 n1 次,询问的数量为 m

接下来一行 n 个整数 f0,f1,,fn1

接下来 m 行,每行一个整数 xi,描述一组询问。

输出格式

输出 m 行,每行一个整数,描述询问取模 998,244,353 后的结果。

样例数据

样例输入

6 6
1 1 4 5 1 4
1
19
191
1919
810
1919810

样例输出

16
10070476
934460929
474354141
579687411
895765304

子任务

对于所有数据,1n,m106

测试点 n,m
1 100
2 5×103
3 3×104
4 105
5 106