574. 通项公式

单点时限: 3.0 sec

内存限制: 1024 MB

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

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

如果一个数列的递推公式为 ,那么他所对应的特征方程为 ,即有

如果方程 个不同的解 且每个根所对应的重数为 ,显然有

我们可以得到数列的通项公式为

其中 ,而 为一个常量,可通过前几项待定系数法求得。

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

给定一个长度为 的序列 ,定义 ,求

输入格式

第一行三个整数 ( ,且 为质数)。

为了减小输入规模,第二行给出三个整数 ( ),其中 ( )。

代表按位异或运算。

输出格式

一行一个整数,代表

样例

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

提示

在第一组数据中, ; ; ;

18 人解决,42 人已尝试。

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

6.7 EMB 奖励。

创建: 1 年,5 月前.

修改: 4 月,4 周前.

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

来源: EOJ Monthly 2019.5

题目标签