#P9224. 「SDOI2021 三轮省集 Day1」高中数列题

    ID: 5306 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-交换求和顺序Lagrange 插值多项式除法阶乘逆元预处理

「SDOI2021 三轮省集 Day1」高中数列题

题目描述

由于出题人实在不会出题了,他只好放一道高中数列题来帮助大家开启愉快的文化课生涯。

数列 an(n≥0)a_n(n\ge 0) 由以下几个参数决定:参数 a,b,ca,b,c 以及 mm 次多项式 f(x)=p0+p1x+p2x2+…+pmxmf(x)=p_0+p_1x+p_2x^2+\ldots +p_m x^m。满足:

$$a_i=\begin{cases}a & i=0\\a_{i-1}+f(i)\times a_{\lfloor\frac {i+b}{c}\rfloor} & i\ge 1\end{cases}$$

给定 n,a,b,c,fn,a,b,c,f,求 ana_n。

输入格式

第一行有五个非负整数 n,a,b,c,mn,a,b,c,m;

第二行有 mm 个非负整数 pip_i。

输出格式

仅一个非负整数表示答案对 10045358091004535809 取模的结果。

样例

3 1 1 3 2
2 1 1
115
$$a_0=1\\a_1=a_0+(1^2+1+2)\times a_0=5\\a_2=a_1+(2^2+2+2)\times a_1=45\\a_3=a_2+(3^2+3+2)\times a_1=115$$

数据范围

测试点编号 n≤n\le m≤m\le 特殊性质
1∼31\sim 3 10610^6 2020 无
44 10710^7
55 10810^8
66 10910^9
77 101010^{10}
88 101210^{12}
9∼119\sim 11 101810^{18} 00
12∼1312\sim 13 11
1414 22
1515 55
16∼1716\sim 17 2020 c>109c>10^9
18∼2018\sim 20 无

对于 100%100\% 的数据,n≤1018n\le 10^{18},m≤20m\le 20,a,b,c,pi<1004535809a,b,c,p_i<1004535809,b<c−1b<c-1。