AC题解

#include<bits/stdc++.h>
using namespace std;
 
int w,k;
struct bigint
{
	int a[215],len;
	bigint ()
	{
		memset(a,0,sizeof(a));
		len=1;
	}
	bigint operator =(int b)
	{
	 	memset(a,0,sizeof(a));len=0;
	 	do
	 	{		 
			a[++len]=b%10;
			b=b/10;
		}while (b);
	 	return *this;
	}
	bigint operator +(const bigint &b)
	{
		bigint c;
		c.len=max(len,b.len);
		for (int i=1;i<=c.len;i++) 
		{
			c.a[i]+=a[i]+b.a[i];
			c.a[i+1]=c.a[i]/10;
			c.a[i]=c.a[i]%10;
		}
		if (c.a[c.len+1]>0) c.len++;
		return c;
	}
	void print()
	{
		for (int i=len;i>=1;i--) cout<<a[i];
	}
}f[2][1024],ans;
int last=0,now=1;
int main()
{
	cin>>k>>w;
	int up=1<<k;
	for (int i=0;i<up;i++) f[last][i]=1;
	for (int i=2;i<=w/k;i++)
	{
		for (int j=up-1;j>=1;j--)
		{
			f[now][j]=f[now][j+1]+f[last][j+1];
			ans=ans+f[now][j];
		}
		swap(last,now);
	}
	for (int j=up-1;j>=1;j--) 
	{
		f[now][j]=f[now][j+1]+f[last][j+1];
		if (j<(1<<(w%k))) ans=ans+f[now][j];
	}
	ans.print();
	return 0;
}