#P7102. [W1] 算

    ID: 6002 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>数论数学O2优化组合数学快速数论变换 NTT

[W1] 算

题目描述

有一个 mm 项多项式 p(x)p(x) 以及两个参数 cctt,其中 p(x)=a0+a1x++am1xm1p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}
定义一个新函数 s(n)s(n):

s(n)=i=1np(i)[gcd(i,n)=1]mod998244353s(n)=\sum_{i=1}^np(i)[\gcd(i,n)=1]\bmod 998244353

请计算 s(c),s(c2),,s(ct)s(c),s(c^2),\dots,s(c^t)

输入格式

第一行三个正整数,分别表示 m,c,tm,c,t
第二行 mm 个正整数,表示 a0,a1,,am1a_0,a_1,\dots,a_{m-1}

输出格式

输出 tt 行,第 ii 行一个正整数 s(ci)s(c^i)

8 10 4
3 1 4 1 5 9 2 6
35683652
171899188
780914481
858211065

提示

对于 10%10\% 的数据,t2,c100t\le2,c\le100;
对于 30%30\% 的数据,t1000,m1000t\le1000,m\le1000
对于 50%50\% 的数据,t5104,m5104,c1012t\le5\cdot10^4,m\le5\cdot10^4,c\le10^{12}
对于另外 10%10\% 的数据,c=123456789c=123456789
对于所有数据,$1\le t\le2\cdot10^5,1\le m\le2\cdot10^5,1\le c\le10^{18}$。