记录编号	107205	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]2^k进制数	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.334 s
提交时间	2014-06-23 12:20:40	内存使用	43.33 MiB

#include <iostream>
#include <cstdio>

using namespace std;

struct bign
{
	int len,num[21];
};

bign bign_init(int a)
{
	bign temp={0};
	while(a)
	{
		temp.num[temp.len++]=a%10000;
		a/=10000;
	}
	return temp;
}

void bign_print(bign a)
{
	if(a.len==0)
	{
		printf("0");
		return;
	}
	
	printf("%d",a.num[a.len-1]);
	
	for(int i=a.len-2;i>=0;i--)
	{
		printf("%04d",a.num[i]);
	}
}

bign bign_plus(bign a,bign b)
{
	if(a.len<b.len) a.len=b.len;

	for(int i=0;i<a.len;i++)
	{
		a.num[i]+=b.num[i];
	}

	for(int i=0;i<a.len;i++)
	{
		if (a.num[i]>10000)
		{
			a.num[i+1]++;
			a.num[i]-=10000;
		}
	}

	if(a.num[a.len]!=0) a.len++;

	return a;
}

int k,w,s,r;
bign ans={0};
bign f[1001][1<<9];

int main()
{
	freopen("digital.in","r",stdin);
	freopen("digital.out","w",stdout);

	scanf("%d%d",&k,&w);

	s=(w-1)/k+1;

	for(int i=0;i<=(1<<k)-1;i++)
	{
		f[s][i]=bign_init(1);
	}

	for(int i=s-1;i>=2;i--)
	{
		for(int j=1;j<=(1<<k)-(s+1-i);j++)
		{
			for(int l=j+1;l<=(1<<k)-(s-i);l++)
			{
				f[i][j]=bign_plus(f[i][j],f[i+1][l]);
			}
	
			if(!(i==s-1&&j==0))
			{
				ans=bign_plus(ans,f[i][j]);
			}
		}
	}

	r=(w-1)%k+1;

	for(int i=1;i<=(1<<r)-1;i++)
	{
		for(int j=i+1;j<=(1<<k)-(s-1);j++)
		{
			f[1][i]=bign_plus(f[1][i],f[2][j]);
		}
		
		ans=bign_plus(ans,f[1][i]);
	}

	bign_print(ans);

	return 0;
}