记录编号	167820	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]2^k进制数	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.667 s
提交时间	2015-06-28 21:51:14	内存使用	0.35 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int k,w,mod=100000;
class miku
{
    public:
	int n;
	int s[20];
	miku(){n=1;memset(s,0,sizeof(s));}
	void operator = (int a)
	{
		memset(s,0,sizeof(s));
		n=1;
		s[0]=a;
	}
	void operator += (const miku &b)
	{
		n=max(n,b.n)+1;
		for(int i=0;i<n;i++)
		{
			s[i]+=b.s[i];
			s[i+1]+=s[i]/mod;
			s[i]%=mod;
		}
		while(n>1&&s[n-1]==0) n--;
	}
	void print()
	{
		printf("%d",s[n-1]);
		for(int i=n-2;i>=0;i--)
			printf("%05d",s[i]);
	}
	void clear()
	{
		n=1;memset(s,0,sizeof(s));
	}
};
miku F[2][520];
miku ans;
int main()
{
	freopen("digital.in","r",stdin);
	freopen("digital.out","w",stdout);
	scanf("%d%d",&k,&w);
	int n=w/k+1;
	int m=1<<k;
	for(int i=1;i<=m;i++)
		F[1][i]=1;
	int now;
	for(int i=2;i<=n;i++)
	{
		if(i==n) now=1<<(w%k);
		else now=m;
		for(int j=1;j<now;j++)
		{
			F[i&1][j].clear();
			for(int k=j+1;k<m;k++)
			{
				F[i&1][j]+=F[(i-1)&1][k];
		    }
			ans+=F[i&1][j];
		}
	}
	ans.print();
	return 0;
}