#1923. poly

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

poly

poly

题目描述

标题: poly - Problem - QOJ.ac

#10358. poly

Statistics

The problem was used in the following contests:

给定n,m,a,b,c。定义f0(x)=1,对于k>0,fk(x)=∑i=0x(ai2+bi+c)fk−1(i)。对于0≤i<n的整数i,求出fi(m)模1004535809的值。

输入格式

一行五个非负整数n,m,a,b,c。

输出格式

n行,每行一个整数,第i行的整数表示fi−1(m)模1004535809的值。

样例数据

样例输入

5 10 0 1 2

样例输出

1
77
3289
103103
2650648

样例解释

f0(x)=1

f1(x)=12x2+52x+2

f2(x)=18x4+1712x3+438x2+9712x+4

f3(x)=148x6+1948x5+4716x4+17516x3+51724x2+1276x+8

f4(x)=1384x8+796x7+491576x6+1307240x5+239711152x4+155732x3+19537288x2+205340x+16

数据范围

数据编号

n

m

a

b

c

0

2000

≤2000

≤109

≤109

≤109

1

300

≤109

2

1000

3

2000

4

250000

0

0

5

≤2000

≤109

≤109

6

≤50000

7

50000

≤109

0

1

0

8

≤109

≤109

9

250000

1

0

10

≤109

11

≤109

12

50000

1

0

0

13

≤109

≤109

≤109

14

100000

1

0

0

15

≤109

≤109

16

≤109

17

250000

1

0

0

18

≤109

≤109

19

≤109

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 10 0 1 2
1
77
3289
103103
2650648