记录编号	463318	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]2^k进制数	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-10-23 21:49:31	内存使用	1.13 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int base=10;
int k,w,ans[200],c[1100][200];
void add(int a[],int b[]){
	a[0]=max(a[0],b[0]);
	int g=0;
	for(int i=1;i<=a[0];i++){
		a[i]+=b[i]+g;
		g=a[i]/base,a[i]%=base;
	}
	while(g)a[++a[0]]=g%base,g/=base;
}
int main(){
	freopen("digital.in","r",stdin);
	freopen("digital.out","w",stdout);
	scanf("%d%d",&k,&w);
	int x,y;
	if(w<=k){printf("0\n");return 0;}
	y=(1<<k)-1;
	if(!(w%k))x=y,k=w/k-1;
	else x=(1<<(w%k))-1,k=w/k;
	c[1][0]=c[1][1]=1;
	ans[0]=0;
	for(int i=1;i<=y;i++){
		for(int j=i+1;j>=1;j--)add(c[j],c[j-1]);
		if(i>=y-x&&i<y)add(ans,c[k+1]);
	}
	for(int i=3;i<=k+1;i++)add(ans,c[i]);
	for(int i=ans[0];i>=1;i--)printf("%d",ans[i]);
	return 0;
}