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 ≤ 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()

本文链接:spoj-9964

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:Rexdf,谢谢!^^


此条目发表在数论分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

:zsmilebig: :zsadbig: :zwiredbig: :zgreenhappy: more »

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据