HDU4656 关于快速数论变换资料，参考ACDdreamer大神博客：here 本题需要公式推导，然后使用NTT来求卷积运算。

$$F_{x_k} = \sum_{i=0}^{n-1} a_i (bc^{2k}+d)^i$$ $$=\sum_{i=0}^{n-1} a_i \sum_{j=0}^{i}C_i^j (bc^{2k})^j d ^ {i-j}$$ $$=\sum_{j=0}^{n-1}(bc^{2k})^j j!^{-1} \sum_{i=j}^{n-1}a_i d^{i-j} i! (i-j)!^{-1}$$ $$=\sum_{j=0}^{n-1}(bc^{2k})^j j!^{-1} \sum_{i=0}^{n-1-j}a_{n-1-i}(n-1-i)! d^{n-1-i-j} (n-1-i-j)!^{-1}$$ $$=\sum_{j=0}^{n-1} (bc^{2k})^j j!^{-1} p_j$$ $$=\sum_{j=0}^{n-1} b^j j!^{-1} p_j c^{2jk}$$ $$=c^{k^2} \sum_{j=0}^{n-1} b^j j!^{-1} p_j c^{j^2} c^{-(k-j)^2}$$ $$=c^{k^2} q_k$$

# Evaluation

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 78 Accepted Submission(s): 15

Problem Description

xk=b*c(2k)+d F(x)=a0 x0+a1 x1+a2 x2+…+an-1 xn-1 Given n, b, c, d, a0, …, an-1, calculate F(x0), …, F(xn-1).

Input

There is only one test case. First line, four integers, n, b, c, d. Second line, n integers, a0, …, an-1.1<=n<=105 1<= b, c, d <=106 0<=ai<=106

Output

n lines. i-th line contains one integer, F(xi-1). Since the answers may be very large, you should output them modulo 106+3.

Sample Input

2 1 2 3 0 1

Sample Output

4 7

Source

2013 Multi-University Training Contest 6

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 457.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%