记录编号	65063	评测结果	AAAAAAAAAAAAAA
题目名称	[暑假培训2012] 残酷的数学老师	最终得分	100
用户昵称	隨風巽	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2013-07-25 15:27:20	内存使用	0.50 MiB

#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
using namespace std;
ifstream fin("cruel1.in");
ofstream fout("cruel1.out");
string N;
int P,num[16000]={0},n,temp[16000]={0},ans[16000]={0};
bool f[100]={0};
void Input(void)
{
	int i,j,l;
	fin>>N>>P;
	l=N.length();
	for(i=1,j=l-1;i<=l;i++,j--)num[i]=N[j]-'0';
	num[0]=l;
	fin.close();
}
void Output(int a[])
{
	int l=a[0],i,j;
	for(i=l,j=0;i>=1;j++,i--)
	{
		if(j%70==0&&j!=0)fout<<endl;
		fout<<a[i];
	}
	fout<<endl;
	fout.close();
}
void Change(int x)
{
	int i;
	for(i=1;x;i++){f[i]=x%2;x/=2;}
	n=i;
}
void mul(int a[],int b[],int res[])
{
	int i,j,l,l1=a[0],l2=b[0];
	for(i=1;i<=l1;i++)
		for(j=1;j<=l2;j++)
			res[i+j-1]+=a[i]*b[j];//是加等
	l=l1+l2-1;
	for(i=1;i<=l;i++)
	{	
		if(res[i]>=10)
		{	
			res[i+1]+=res[i]/10;
		    res[i]%=10;
		}
    }
	if(res[i])l++;
	res[0]=l;
}
void ow(int a[],int b[])
{
	int i,l=b[0];
	for(i=0;i<=l;i++)a[i]=b[i];
}
void Process(void)
{
	int i;
	ans[0]=1;
	ans[1]=1;
	if(f[1])
	{
		mul(ans,num,temp);
	    ow(ans,temp);
	}
	for(i=2;i<n;i++)
	{
		memset(temp,0,sizeof(temp));
		mul(num,num,temp);
		ow(num,temp);
		if(f[i])
		{
			memset(temp,0,sizeof(temp));   //15=8+4+2+1  2*4*8*16
			mul(ans,num,temp);
			ow(ans,temp);
		}
	}
}
int main()
{
	Input();
	Change(P);
	Process();
	Output(ans);
	return 0;
}