#P4233. [Cerc2013]Captain Obvious and the Rabbit-Man

    ID: 3451 传统题 1000ms 128MiB 尝试: 87 已通过: 48 难度: 6 上传者: 标签>难度分类提高线性代数与代数线性递推多项式与生成函数普通多项式乘法CF2100

[Cerc2013]Captain Obvious and the Rabbit-Man

[CERC 2013] Captain Obvious and the Rabbit-Man

题目描述

兔人每天选一个地点,地点的编号由一个数列给出。定义

$$F_i=\begin{cases} 1,&i=1,\\ 2,&i=2,\\ F_{i-1}+F_{i-2},&i\ge3. \end{cases}$$

设 kk 为正整数,a1,a2,…,aka_1,a_2,\ldots,a_k 是固定但未知的整数。第 ii 项为

pi=∑j=1kajFji.p_i=\sum_{j=1}^{k}a_j F_j^i.

给定 kk、质数 MM 以及 p1,p2,…,pkp_1,p_2,\ldots,p_k 对 MM 取模后的值,求 pk+1p_{k+1} 对 MM 取模后的值。保证 F1,…,FkF_1,\ldots,F_k 对 MM 取模后两两不同,且所求的余数唯一。

输入格式

第一行两个整数 k,Mk,M。

第二行 kk 个整数,依次表示 p1,p2,…,pkp_1,p_2,\ldots,p_k 对 MM 取模后的值。

输出格式

输出一行一个整数,表示 pk+1p_{k+1} 对 MM 取模后的结果。

样例 #1

样例输入 #1

3 101
5 11 29

样例输出 #1

83

样例 #2

样例输入 #2

4 619
5 25 125 6

样例输出 #2

30

样例说明

第一组样例的通项可写为 pi=2⋅1i+3ip_i=2\cdot1^i+3^i,第二组样例可写为 pi=5ip_i=5^i,均按各自的 MM 取模。

数据规模与约定

1≤k≤4 0001\le k\le4\,000,3≤M≤1093\le M\le10^9,MM 为质数。

题目原型见 CERC 2013 官方题册。