#H1014. Chirp Z-Transform modulo 10^9+7

Chirp Z-Transform modulo 10^9+7

题目描述

给定一个 nn 项多项式 P(x)P(x) 以及 c,mc, m,请计算 P(c0),P(c1),,P(cm1)P(c^0),P(c^1),\dots,P(c^{m-1})。所有答案都对 109+710^9+7 取模。

输入格式

第一行三个正整数 n,c,mn,c,m
第二行 nn 个非负整数 a0,a1,,an1a_0,a_1,\dots,a_{n-1},由低到高表示 P(x)P(x) 的系数。

输出格式

一行 mm 个正整数,第 ii 个数表示 P(ci1)P(c^{i-1})

6 108616 6
1 0 8 6 1 6
22 772456230 866731294 299746576 978045696 394365866

数据规模与约定

对于 100%100\% 的数据,1n,m61051\le n,m\le 6\cdot10^50c,ai<109+70\le c,a_i<10^9+7.

测试点编号 n,mn,m 限制
11 n=m=103n=m=10^3
22 n=m=6.4×104n=m=6.4\times 10^4
33 n=m=5105n=m=5\cdot10^5
44 n=5105,m=6105n=5\cdot10^5,m=6\cdot10^5
55 n=6105,m=5105n=6\cdot10^5,m=5\cdot10^5

出题人很遗憾由于精度和洛谷自带资料限制无法开到 10610^6

提示:77 次 FFT 可能过不了。

提示:出题人没有用 long double