spoj-9964

9964. Fibonacci vs Polynomial
Problem code: PIBO
Define a sequence Pib(n) as following

• Pib(0) = 1
• Pib(1) = 1
• otherwise, Pib(n) = Pib(n-1) + Pib(n-2) + P(n)

Here P is a polynomial.

Given n and P, find Pib(n) modulo 1,111,111,111.

Input

First line of input contains two integer n and d (0 ≤ n ≤ 10⁹, 0 ≤ d ≤ 100), d is the degree of polynomial.

The second line contains d+1 integers c₀,c₁ … c_d, represent the coefficient of the polynomial(Thus P(x) can be written as Σc_ixⁱ). 0 ≤ c_i ≤ 100 and c_d ≠ 0 unless d = 0.

Output

A single integer represents the answer.

Example

<b>Input:</b>
10 0
0

<b>Output:</b>
89

<b>Input:</b>
10 0
1

<b>Output:</b>
177

<b>Input:</b>
100 1
1 1

<b>Output:</b>
343742333

题解

(第一次用latex详细写计算过程，调试了一下午的数学公式)：
我们都知道可以这么快速计算斐波那契数列：令 $F=\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)$, 那么 $F^n\left(\begin{array}{cc} \text{Fib} (n) \\ \text{Fib} (n-1) \end{array}\right)=\left(\begin{array}{cc} \text{Fib} (n+1) \\ \text{Fib} (n) \end{array}\right)$ . 我们也知道二项式公式：${(n + 1)^k} = \sum\limits_{i = 0}^k {C_k^i} {n^i}$,
${(n + 1)^d} = C_d^0{n^d} + C_d^1{n^{d – 1}} + \cdots + C_d^d{n^0}$,
${(n + 1)^{d – 1}} = C_{d – 1}^0{n^{d – 1}} + C_{d – 1}^1{n^{d – 2}} + \cdots + C_{d – 1}^{d – 1}{n^0}$,
$\cdots$.

令 $A=\left( \begin{array}{cccccc} 1 & 1 & c_d & c_{d-1} & \cdots & c_0 \\ 1 & 0 & 0 & \cdots & \cdots & 0 \\ 0 & 0 & C_d^d & C_d^{d-1} & \cdots & C_d^0 \\ 0 & 0 & 0 & C_{d-1}^{d-1} & \cdots & C_{d-1}^0 \\ \vdots & \vdots & \cdots & \cdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & C_0^0 \end{array} \right)$,$p_{n}=\left( \begin{array}{c} \text{Pibo} (n) \\ \text{Pibo} (n-1) \\ n^d \\ n^{d-1} \\ \vdots \\ n^0 \\ \end{array} \right)$
那么：
$$Ap_n=p_{n+1}$$
也就是：
$$\left( \begin{array}{cc|cccc} 1 & 1 & c_d & c_{d-1} & cdots & c_0 \\ 1 & 0 & 0 & cdots & cdots & 0 \\ \hline 0 & 0 & C_d^d & C_d^{d-1} & \cdots & C_d^0 \\ 0 & 0 & 0 & C_{d-1}^{d-1} & \cdots & C_{d-1}^0 \\ \vdots & \vdots & \cdots & \cdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & C_0^0 \end{array} \right)\left( \begin{array}{c} \text{Pibo} (n-1) \\ \text{Pibo} (n-2) \\ n^d \\ n^{d-1} \\ \vdots \\ n^0 \end{array} \right)=\left( \begin{array}{c} \text{Pibo} (n) \\ \text{Pibo} (n-1) \\ (n+1)^d \\ (n+1)^{d-1} \\ \vdots \\ (n+1)^0 \end{array} \right)$$
复杂度是：$O((d+3)^3 \log{n})$ 也就是$103^3 \log {10^9}$

进行优化：

令$\text{B}(n)=\text{Pibo} (n)+\sum\limits_{i = 0}^d {k_i} {n^i}=\text{Pibo} (n)+k_dn^d+k_{d-1}n^{k-1}+\cdots+k_0$，那么
$$\text{B}(n)=\text{B}(n-1)+\text{B}(n-2)$$
也就有 $$\left(\begin{array}{c} \text{B}(n) \\ \text{B}(n-1) \end{array}\right)=\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)^{n-1}\left(\begin{array}{c} \text{B}(1) \\ \text{B}(0) \end{array}\right)$$
现在复杂度是$O(8\log{n})$ to calculate $B_n$，$8 \log {10^9}$

但是我们需要知道$k_0 \cdots k_d$ 来计算初始值$\text{B}(1)),(\text{B}(0)$ 以及从$\text{B}(n)$反解出 $\text{Pibo} (n)$。

从$\text{B}(n)=\text{B}(n-1)+\text{B}(n-2)$ 我们可以得到:
$$\text{Pibo} (n) + \sum\limits_{i = 0}^d {k_i} {n^i} = [\text{Pibo} (n-1) + \sum\limits_{i = 0}^d {k_i} {(n-1)^i}] + [\text{Pibo} (n-2)+\sum\limits_{i = 0}^d {k_i} {(n-2)^i}]$$
和原来的比较:
$$\text{Pibo} (n) = \text{Pibo} (n-1) + \text{Pibo} (n-2)+\sum\limits_{i = 0}^d {c_i} {n^i}$$
可以得出
$$\sum\limits_{i = 0}^d {k_i} {(n-1)^i}+\sum\limits_{i = 0}^d {k_i} {(n-2)^i}-\sum\limits_{i = 0}^d {k_i} {n^i} \equiv \sum\limits_{i = 0}^d {c_i} {n^i}$$
也就是
$$\sum\limits_{i = 0}^d [{k_i} {(n-1)^i}+{k_i}{(n-2)^i}-{k_i}{n^i}] \equiv \sum\limits_{i = 0}^d {c_i} {n^i}$$

化简这个式子得到：
$$\left( \begin{array}{ccccc} C_0^0 & C_1^1\left[(-1)^1+(-2)^1\right] & C_2^2\left[(-1)^2+(-2)^2\right] & \cdots & C_d^d\left[(-1)^d+(-2)^d\right] \\ 0 & C_1^0 & C_2^1\left[(-1)^1+(-2)^1\right] & \cdots & C_d^{d-1}\left[(-1)^{d-1}+(-2)^{d-1}\right] \\ 0 & 0 & C_2^0 & \cdots & C_d^{d-2}\left[(-1)^{d-2}+(-2)^{d-2}\right] \\ \cdots & \cdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & C_d^0 \end{array} \right)\left( \begin{array}{c} k_0 \\ k_1 \\ k_2 \\ \vdots \\ k_d \end{array} \right) \\ =\left( \begin{array}{c} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_d \end{array} \right)$$
可以容易发现这是一个上三角且主对角线是1的矩阵，利用下面的式子可以进一步化简，而且不需要进行计算$C_n^k$时候的阶乘计算，而全部化成加法运算，进一步优化
$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}$$

python代码

如下：