程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3306 Another kind of Fibonacci

hdu 3306 Another kind of Fibonacci

編輯:C++入門知識

hdu 3306 Another kind of Fibonacci


Another kind of Fibonacci

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1526 Accepted Submission(s): 583


Problem Description As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)2 +A(1)2+……+A(n)2.


Input There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 1

Output For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
Sample Input
2 1 1 
3 2 3 

Sample Output
6
196

Author wyb
Source HDOJ Monthly Contest – 2010.02.06
題解及代碼:

#include 
#include 
#include 
using namespace std;
const int mod=10007;
struct mat
{
    __int64 t[4][4];
    void set()
    {
        memset(t,0,sizeof(t));
    }
} a,b;

mat multiple(mat a,mat b,__int64 n,int p)
{
    int i,j,k;
    mat temp;
    temp.set();
    for(i=0; i>=1;
        b=multiple(b,b,n,p);
    }
    return t;
}

void init(__int64 x,__int64 y)
{
   b.set();
   b.t[0][0]=1;
   b.t[1][0]=x*x%mod;b.t[1][1]=x*x%mod;b.t[1][2]=x;b.t[1][3]=1;
   b.t[2][0]=2*x*y%mod;b.t[2][1]=2*x*y%mod;b.t[2][2]=y;
   b.t[3][0]=y*y%mod;b.t[3][1]=y*y%mod;
}
int main()
{
    __int64 n,x,y;
    while(cin>>n>>x>>y)
    {
        x=x%mod;
        y=y%mod;
        init(x,y);
        a=quick_mod(b,4,n-1,mod);
        cout<<(2*a.t[0][0]+a.t[1][0]+a.t[2][0]+a.t[3][0])%mod<




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved