订阅
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 ≤ 109, 0 ≤ d ≤ 100), d is the degree of polynomial.
The second line contains d+1 integers c0,c1 … cd, represent the coefficient of the polynomial(Thus P(x) can be written as Σcixi). 0 ≤ ci ≤ 100 and cd ≠ 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代码
如下：
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 06 16:56:53 2014
@author: rexdf
"""
"""
1 2014-02-06 11:39:02 rexdf accepted 0.06 4.0M PYTH 2.7
"""
modulo=1111111111 #It's not a prime number!!!
def matrix2_2Mul(A,B):
return [[(A[0][0]*B[0][0]+A[0][1]*B[1][0])%modulo,(A[0][0]*B[0][1]+A[0][1]*B[1][1])%modulo],[(A[1][0]*B[0][0]+A[1][1]*B[1][0])%modulo,(A[1][0]*B[0][1]+A[1][1]*B[1][1])%modulo]]
def matrix2_2Pow(A,n):
ret=[[1,0],[0,1]]
while n:
if n&1:
ret=matrix2_2Mul(ret,A)
A=matrix2_2Mul(A,A)
n>>=1
return ret
def main():
n,d = map(int,raw_input().split())
dat = map(int,raw_input().split())
if n<2:
print 1
else:
comb=[[0]*(d+1) for i in range(0,d+1)]
for i in range(0,d+1):
comb[0][i]=comb[i][i]=1
for i in range(1,d):
for j in range(i+1,d+1):
comb[i][j]=comb[i][j-1]+comb[i-1][j-1]
if comb[i][j]>modulo:comb[i][j]-=modulo
fn1=[0]*(d+1)
fn1[0]=1
for i in range(1,d+1):
fn1[i]=fn1[i-1]*(-1)
fn2=[0]*(d+1)
fn2[0]=0
if d:
fn2[1]=-2
for i in range(2,d+1):
fn2[i]=(fn2[i-1]*(-2))%modulo
alf=[0]*(d+1)
alf[d]=dat[d]
#print "alf_d = ",alf[d],dat[d]
for i in range(d-1,-1,-1):
tmp=dat[i]
for j in range(d,i,-1):
tmp-=comb[i][j]*(fn1[j-i]+fn2[j-i])*alf[j]
#tmp/=calc_dat[i][i]
alf[i]=tmp%modulo
#for i in range(0,d+1):print i,alf[i]
B=[[1+sum(alf)%modulo],[1+alf[0]%modulo]]
#print B[0],B[1]
A=[[1,1],[1,0]]
C=matrix2_2Pow(A,n-1)
#Bn=matrixMul2(C,B)
Bn=(C[0][0]*B[0][0]+C[0][1]*B[1][0])%modulo
ans=0
pown=1
for i in range(0,d+1):
ans+=pown*alf[i]
ans%=modulo
pown*=n
pown%=modulo
ans=Bn-ans
ans%=modulo
if ans<0:
ans+=modulo
print ans
if __name__ == '__main__':
main()