1017. 二哥養兔子
Description
二哥培養出了一種繁殖能力很強的兔子。
這種兔子在出生後的第一個月,能夠生出a對兔子;第二個月,能夠生出b對兔子;第三個月以及以後的每個月,都可以生出c對兔子。
二哥對此很感興趣,若他有一對剛出生的兔子,按照最理想的模式繁殖,并假設兔子不死,二哥想知道最少需要幾個月這些兔子可以遍布地球的每個角落。
為了回答這個問題,二哥想要知道這種兔子在第N個月時的對數。
Input Format
輸入隻有一行,四個數,分别為a,b,c,N ( 0≤a≤b≤c≤100,N≤1000
),其含義為題目所述。
Output Format
輸出隻有一個數,為第N個月兔子的對數。
Sample Input
0 1 1 11
Sample Output
144
題目所給的資料為斐波那契數列,對于兔子問題,大家自行百度斐波那契 兔子問題即可明白,這裡有這樣一個表達式:
res[i]=res[i-3]*c+(res[i-2]-res[i-3])*b+(res[i-1]-res[i-2])*a+res[i-1];
比如第4個月的兔子數,為第一個月的兔子生下的res[1]*c,和第二個月的新生兔子乘以b,加上第三個月新生兔子乘以a再加上這之前的老兔子數即可。
但是這裡其實更麻煩的一點是對于大數字的處理,由于N在1000的時候已經遠遠大于正常的表達範圍,是以必須自己用類模仿大數字。
#include <iostream>
#include "string.h"
using namespace std;
class bigInt
{
friend bigInt operator+(bigInt a,bigInt b);
friend bigInt operator-(bigInt a,bigInt b);
friend bigInt operator*(bigInt a,bigInt b);
public:
int ans[3000];
int length;
bigInt()
{
memset(ans,0,sizeof(int)*1000);
length=0;
}
bigInt(int a)
int i=0;
while(a!=0)
{
ans[i++]=a%10;
a=a/10;
}
length=i;
bigInt(const bigInt& a)
length=a.length;
for(int i=0;i<length;i++)
ans[i]=a.ans[i];
bigInt& operator=(const bigInt &a)
if(&a==this) return (*this);
return (*this);
void print()
for(int i=length-1;i>=0;i--)
cout<<ans[i];
cout<<endl;
};
bigInt operator*(bigInt a,int b)
bigInt c;
int carry=0;
for(int i=0;i<a.length;i++)
int tp=a.ans[i]*b+carry;
carry=tp/10;
c.ans[i]=tp%10;
int j=a.length;
while(carry!=0)
c.ans[j++]=carry%10;
carry=carry/10;
c.length=j;
return c;
}
bigInt operator-(bigInt a,bigInt b)
int length_small=(a.length>b.length)?b.length:a.length;
for(int i=0;i<length_small;i++)
if(a.ans[i]<(b.ans[i]+carry))
c.ans[i]=10+a.ans[i]-b.ans[i]-carry;
carry=1;
else
c.ans[i]=a.ans[i]-b.ans[i]-carry;
carry=0;
if(a.length>b.length)
for(int i=b.length;i<a.length;i++)
if(a.ans[i]<carry)
{
c.ans[i]=10+a.ans[i]-carry;
carry=1;
}
else
c.ans[i]=a.ans[i]-carry;
carry=0;
else if(a.length<b.length)
for(int i=a.length;i<b.length;i++)
c.ans[i]=10+b.ans[i]-carry;
c.ans[i]=b.ans[i]-carry;
for(int i=max(a.length,b.length);i>=0;i--)
if(c.ans[i]!=0)
c.length=i+1;
break;