574. 通项公式

单点时限: 3.0 sec

内存限制: 1024 MB

QQ小方以前不会算递推数列的通项公式,现在他会了,所以他急切的想教会你。

一种常见的递推数列通项公式求法是使用特征方程。

如果一个数列的递推公式为 $a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}$ ,那么他所对应的特征方程为 $r^n=c_1r_{n-1}+c_2r_{n-2}+\cdots +c_kr_{n-k}$ ,即有 $r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots -c_{k-1}r-c_k=0$ 。

如果方程 $r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots -c_{k-1}r-c_k=0$ 有 $t$ 个不同的解 $r_1,r_2,r_3\cdots r_t$ 且每个根所对应的重数为 $m_1,m_2,m_3\cdots m_t$ ,显然有 $m_i\ge 1(i\in [1,t])$ 且 $\sum_{i=1}^t m_i=k$ 。

我们可以得到数列的通项公式为 $$a_n=(\alpha {1,0}+\alpha n+\cdots +\alpha {1,m-1}n^{m_{1}-1})r_1^n\+(\alpha {2,0}+\alpha n+\cdots +\alpha {2,m-1}n^{m_{2}-1})r_2^n\+\cdots \+(\alpha {t,0}+\alpha n+\cdots +\alpha {1,m-1}n^{m_{t}-1})r_t^n$$ 。

其中 $n=1,2,3,\cdots $ ,而 $\alpha _{i,j}(1\le i\le t,0\le j\le m_i-1)$ 为一个常量,可通过前几项待定系数法求得。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

给定一个长度为 $n$ 的序列 ${a_n}$ ,定义 $f_1(m)=\sum_{i=1}^m a_i$ , $f_i(m)=\sum_{j=1}^m f_{i-1}(j)(i>1)$ ,求 $f_k(n) \mod p$ 。

输入格式

第一行三个整数 $n,k,p$ ( $1 \le n,k \le 10^7,1 \le p \le 100$ ,且 $p$ 为质数)。

为了减小输入规模,第二行给出三个整数 $a_1,mul,add$ ( $0 \le a_1,mul,add < p$ ),其中 $a_{i+1}=((a_i \times mul + add) \oplus i) \mod p$ ( $i\ge 1$ )。

$\oplus$ 代表按位异或运算。

输出格式

一行一个整数,代表 $f_k(n) \mod p$ 。

样例

Input
3 3 7
0 3 4
Output
4
Input
5 5 13
10 3 9
Output
4

提示

在第一组数据中, ${a_i}=0,5,3$ ; ${f_1(i)}=0,5,1$ ; ${f_2(i)}=0,5,6$ ; ${f_3(i)}=0,5,4$ 。

18 人解决,42 人已尝试。

24 份提交通过,共有 335 份提交。

6.7 EMB 奖励。

创建: 2 年,1 月前.

修改: 1 年,1 月前.

最后提交: 5 月,2 周前.

来源: EOJ Monthly 2019.5

题目标签