G - 很麻煩的題（HDU1250）

题目来源：

https://cn.vjudge.net/contest/290635#problem/G

http://acm.hdu.edu.cn/showproblem.php?pid=1250

Problem Description

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.

Input

Each line will contain an integers. Process to end of file.

Output

For each case, output the result in a line.

Sample Input

Sample Output


 4203968145672990846840663646

Note: No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

Author

戴帽子的

Recommend

Ignatius.L

思路：高精度水题(或许这和ToRe在路上给我讲的滚动数组差不多意思吧，就是一个用四个变量存一下中间值而已,直接求就可以，就我傻不laji在打表所以一直超内存，也没想着不打表）

参考代码：

//直接求，，，
import java.math.BigInteger;
import java.util.Scanner;

public class Main{
static BigInteger [] a = new BigInteger[7008];    
public static void main(String []args){
        Scanner cin = new Scanner((System.in));
        while (cin.hasNext()){
            int t = cin.nextInt();
        a[1] = new BigInteger("1");
        a[2] = new BigInteger("1");
        a[3] = new BigInteger("1");
        a[4] = new BigInteger("1");
        for(int i = 5;i<=t;i++){
            a[i] = (a[i-1].add(a[i-2]).add(a[i-3]).add(a[i-4]));
        }
            System.out.println(a[t]);
        }
        cin.close();
    }
}
//最后一分钟想通的，这样推一下也行
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext()){
			int n=cin.nextInt();
			BigInteger ans = new BigInteger("1");
			BigInteger a = new BigInteger("1");
			BigInteger b = new BigInteger("1");
			BigInteger c = new BigInteger("1");
			BigInteger d = new BigInteger("1");
			for(int i=5;i<=n;i++){
				ans=a.add(b).add(c).add(d);
				a=b;
				b=c;
				c=d;
				d=ans;
			}
			System.out.println(ans);
		}
        cin.close();
	}
}

QAQ：***的是我居然后来用bin巨的Bigint类打出来7035的表（代码打代码）还妄想交上去emmm（其实长度不超过2005的话，n就7035，不打表复杂度也够emmm）

可恶的是打比赛打着电脑突然关机然后后面代码都没了，后来用bin巨的Bigint类打了一个，，，最后一分钟写出上面代码，没来得及交上去，我能笑一年

//仅供娱乐= =
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#define mm(a,b) memset(a,b,sizeof(a))
#define N 305
#define inf 0x3f3f3f3f
using namespace std;
struct BigInt
{
    const static int mod = 10000;
    const static int dlen = 4;
    int a[2008],len;
    BigInt()
    {
        mm(a,0);
        len = 1;
    }
    BigInt(int v)
    {
        mm(a,0);
        len = 0;
        do
        {
            a[len++] = v%mod;
            v/=mod;
        }
        while(v);
    }
    BigInt(const char s[])
    {
        mm(a,0);
        int l = strlen(s);
        len = l/dlen;
        if(l%dlen)len++;
        int id=0;
        for(int i=l-1; i>=0; i-=dlen)
        {
            int t = 0;
            int k=i-dlen+1;
            if(k<0)
                k=0;
            for(int j=k; j<=i; j++)
                t=t*10+s[j]-'0';
            a[id++]=t;
        }
    }
    BigInt operator +(const BigInt &b)const
    {
        BigInt res;
        res.len=max(len,b.len);
        for(int i=0; i<=res.len; i++)
            res.a[i]=0;
        for(int i=0; i<res.len; i++)
        {
            res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);
            res.a[i+1]+=res.a[i]/mod;
            res.a[i]%=mod;
        }
        if(res.a[res.len]>0)res.len++;
        return res;
    }
    void output()
    {
        printf("%d",a[len-1]);
        for(int i=len-2; i>=0; i--)
            printf("%d",a[i]);
        printf("\';\n");
    }
}fib[61005];
void init()
{
    fib[1]=1;
    fib[2]=1;
    fib[3]=1;
    fib[4]=1;
    for(int i=5;i<=7035;i++)
        fib[i]=fib[i-1]+fib[i-2]+fib[i-3]+fib[i-4];
}
int main()
{
    int t;
    init();
    freopen("C:\\Users\\nuoyanli\\Desktop\\acmoutput.txt","w",stdout);
    cout<<"#include<iostream>\n";
    cout<<"using namespace std;\n";
    cout<<"int main()\n{\n    int t;\n    cin>>t;\n    char a[7040];\n";
    for(int i=1;i<=7035;i++)
    {
         printf("a[%d]=\'",i);
         fib[i].output();
    }
    cout<<" cout<<a[t]<<endl;\n";
    cout<<"return 0;\n}";
    return 0;
}

事实证明oj是不会让你交7000行+的代码的

G - 很麻煩的題 （HDU1250）

G - 很麻煩的題（HDU1250）