PKU 3982-序列

問題概要

A(n)=A(n-1)+A(n-2)+A(n-3)(n>=3)とする．
A(0),A(1),A(2)が与えられるので，A(99)の値を求めよ

考え方

多倍長で計算するだけ

実装(C++)

#include <vector>
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
#include <map>
using namespace std;
const int BI_MAX=10000;
struct BigInteger{
        deque<short> val;
        int flags;
        BigInteger(int n=0){
                flags=0;
                if(n)flags=n/abs(n);
                while(n)val.push_back(n%BI_MAX),n/=BI_MAX;
        }
        void clear_leading_zero(){while(val.back()==0)val.pop_back();}
        string to_string(){
                if(val.size()==0)return "0";
                char res[val.size()*4+5];char *r;r=res+val.size()*4+4;*(r--)='\0';
                for(int i=0;i<(int)val.size();i++){
                        int t=val[i];
                        for(int j=0;j<4;j++){
                                if(t==0&&i==(int)val.size()-1)break;
                                (*r--)=t%10+'0';
                                t/=10;
                        }
                }
                return string(r+1);
        }
};
BigInteger add(const BigInteger &a,const BigInteger &b){
        BigInteger res(0);
        short va,vb,k=0;
        for(int i=0;i<max<int>(a.val.size(),b.val.size());i++){
                        if(i<(int)a.val.size())va=a.val[i];else va=0;
                        if(i<(int)b.val.size())vb=b.val[i];else vb=0;
                        va+=k;
                        k=(va+vb)>=BI_MAX;
                        res.val.push_back(va+vb-(k?BI_MAX:0));
        }
        if(k)res.val.push_back(k);
        return res;
}
BigInteger mul(const BigInteger &a,const BigInteger &b){
        int k=0,i,j;
        BigInteger res(0);
        for(int i=0;i<(int)a.val.size()+(int)b.val.size()+1;i++){
                res.val.push_back(0);
        }
        for(i=0;i<(int)a.val.size();i++){
                k=0;
                for(j=0;j<(int)b.val.size();j++){

                        k=a.val[i]*b.val[j]+k;
                        res.val[i+j]+=k%BI_MAX;
                        k/=BI_MAX;
                        if(res.val[i+j]>=BI_MAX){
                                res.val[i+j]-=BI_MAX;k++;
                        }
                }
                while(k){
                        res.val[i+j]+=k;
                        if(res.val[i+j]>=BI_MAX){res.val[i+j]-=BI_MAX;k=1;}else k=0;
                        j++;
                }
        }
        res.clear_leading_zero();
        return res;
}

BigInteger operator+(const BigInteger &a,const BigInteger &b){return add(a,b);}
BigInteger operator*(const BigInteger &a,const BigInteger &b){return mul(a,b);}
int a[3];
map<int,BigInteger> dp;
BigInteger solve(int x){
	if(x<=2)return a[x];
	if(dp.find(x)!=dp.end())return dp[x];
	dp[x]=solve(x-1)+solve(x-2)+solve(x-3);
	return dp[x];
}

int main() {
	for(;cin>>a[0]>>a[1]>>a[2];){
		dp.clear();
		cout<<solve(99).to_string()<<endl;
	}
	return 0;
}