pku 2506 高精度加乘+递推.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;

//PKU 2506 高精度加乘+递推
#define NMAX 260
#define MMAX 150

int f[NMAX][MMAX];

void mullow(int a[],int b,int ans[])
{
	int i,len;
	int tmp[NMAX]={0};
	len=a[0];
	for(i=1;i<=len;i++)
	{
		tmp[i]+=a[i]*b;
		tmp[i+1]=tmp[i]/10;
		tmp[i]%=10;
	}
	len++;
	while(tmp[len]>=10)
	{
		tmp[len+1] = tmp[len]/10;
		tmp[len] %=10;
		len++;
	}
	while(len>1 && tmp[len]==0) len--;
	tmp[0]=len;
	for(i=0;i<=tmp[0];i++) ans[i]=tmp[i];
}

void add(int a[],int b[],int ans[])
{
	int i,len;
	int tmp[MMAX];
	len=(a[0]>b[0])? a[0]:b[0];
	for(i=1;i<=len;i++)
	{
		tmp[i]+=a[i]+b[i];
		if(tmp[i]>=10)
		{
			tmp[i]-=10;
			tmp[i+1]+=1;
		}
	}
	if(tmp[len+1]>0) len++;
	tmp[0]=len;
	for(i=0;i<=tmp[0];i++) ans[i]=tmp[i];
}
void solve(int num)
{
	int i;
	int ff[MMAX];
	f[0][1]=f[0][0]=f[1][1]=f[1][0]=1;
	for(i=2;i<=num;i++)
	{
		mullow(f[i-2],2,ff);
		add(f[i-1],ff,f[i]);
//		f[i]=f[i-1]+2*f[i-2];
	}
}

int main()
{
	int i,num;
	solve(251);
	while(scanf("%d",&num)!=EOF)
	{
		for(i=f[num][0];i>=1;i--)
		{
			printf("%d",f[num][i]);
		}
		printf("\n");
	}	
	return 0;
}