记录编号	78175	评测结果	AAAAAAAAAA
题目名称	方程	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.946 s
提交时间	2013-11-03 16:14:07	内存使用	1.08 MiB

#include<fstream>
#include<iomanip>
#include<cstring>
#include<algorithm>
using namespace std;
ifstream fi("equationz.in");
ofstream fo("equationz.out");
unsigned long long X;
int K;
int quickpow(int a,unsigned long long b)
{
	if(b==1)return a;
	int tmp=quickpow(a,b/2);
	tmp=(tmp*tmp)%1000;
	if(b%2==1)tmp=(tmp*a)%1000;
	return tmp;
}
class HIGH
{
public:
	int d[101];
	HIGH(){memset(d,0,sizeof(d));}
}C[2][1001];
HIGH operator + (HIGH a,HIGH b)
{
	HIGH ans;
	ans.d[0]=max(a.d[0],b.d[0]);
	for(int i=1;i<=ans.d[0];i++)
	{
		ans.d[i]+=a.d[i]+b.d[i];
		while(ans.d[i]>9999)
			ans.d[i+1]++,ans.d[i]-=10000;
	}
	while(ans.d[ans.d[0]+1]>0)
	{
		ans.d[0]++;
		while(ans.d[ans.d[0]]>9999)
			ans.d[ans.d[0]+1]++,ans.d[ans.d[0]]-=10000;
	}
	return ans;
}
int main()
{
	fi>>K>>X;
	int gX=quickpow(int(X%1000),X);
	C[1][1].d[0]=C[1][1].d[1]=1;C[0][1].d[0]=C[0][1].d[1]=1;
	for(int i=2;i<=gX;i++)
	{
		int pre=(i-1)&1,now=i&1;
		for(int j=2;j<=i;j++)
		{
			C[now][j]=C[pre][j-1]+C[pre][j];
			//fo<<C[now][j]<<' ';
		}
		//fo<<endl;
	}
	//fo<<setiosflags(ios::fixed)<<setprecision(0)<<C[(gX)&1][K]<<endl;
	HIGH ans=C[gX&1][K];
	fo<<ans.d[ans.d[0]];
	for(int i=ans.d[0]-1;i>0;i--)
	{
		fo<<ans.d[i]/1000;
		fo<<(ans.d[i]/100)%10;
		fo<<(ans.d[i]/10)%10;
		fo<<ans.d[i]%10;
	}
	return 0;
}