power.cpp

多重幂计数问题 &laquo 问题描述： 设给定n 个变量1 x , 2 x ,…, n x 。将这些变量依序作底和各层幂

/*
算法改进：
1，用一个数组存储已经计算过的多重幂数，需要时直接读出，不需要在重新计算。
2，因为f(i)*f(n-i)=f(n-i)*f(i),所以连加只需要计算到n/2既可。
*/
#include<iostream>
#include<fstream.h>
#include<stdlib.h>
ifstream inf("input.txt");
ofstream outf("output.txt");
__int64 * past;//存放已计算过的多重幂数；初始化为0，表示未计算过。
__int64 f(int n)
{
	if(past[n]!=0)return past[n];//已计算过，直接返回。
	__int64 i;
	__int64 j=0;
	for(i=1;i<=n/2;i++)
	{
		j+=f(i)*f(n-i);
	}
	j+=j;
	if(n%2==0)
		j=j-past[n/2]*past[n/2];
	past[n]=j;//保存计算过的幂数。
	return j;
}

void main()
{
	int n;
	inf>>n;
	past=new __int64[n+1];
	int i;
	for(i=0;i<n+1;i++)
	{
		past[i]=0;
	}
	past[1]=1;
	char temp[21];
	outf<<_i64toa(f(n),temp,10);//将__int64的整型转化成字符串输出。
	delete[]past;
}