记录编号	293132	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 1997] n-k集合数	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2016-08-09 19:02:27	内存使用	2.60 MiB

/*高精度+动归，f[i][j]表示前i个数中，大于等于j的集合有多少个。
则目标值为f[n][k+1],意义是在总共n个数中，大于等于k+1的集合有多少个。
则每一个f[i][j]有两个转移状态，第一个，i在集合中，则i-1不能在集合中，
所以转移应为f[i-2][max(0,j-i)]，第二个，i不在集合中，则i-1
可以再集合中，所以转移应为f[i-1][j];
由于i在不在集合中，都属于f[i][j]可能情况，
故f[i][j]=f[i-1][j]+f[i-2][max(j-i,0)]; 
*/
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxn=110;
void bigsum(int a[],int b[],int c[])
{
	int len=max(a[0],b[0]);
	for(int i=1;i<=len;++i)
	{
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;
	}
	if(c[len+1])	len++;
	c[0]=len;
}
int f[maxn][410][55];
int n,k;
ll ans=0,cnt=0;
int ma(){
	//freopen("余.txt","r",stdin);
	freopen("lic.in","r",stdin);
	freopen("lic.out","w",stdout);
	memset(f,0,sizeof f);
	scanf("%d%d",&n,&k);
	f[1][0][0]=1;f[1][1][0]=1;f[2][0][0]=1;
	f[2][1][0]=1;f[2][2][0]=1;
	f[1][0][1]=2;f[1][1][1]=1;f[2][0][1]=3;
	f[2][1][1]=2;f[2][2][1]=1;
	for(int i=3;i<=n;i++)
	for(int j=0;j<=k+1;j++)
		bigsum(f[i-1][j],f[i-2][max(j-i,0)],f[i][j]);
	bool flag=0;
	for(int i=f[n][k+1][0];i>=1;i--){
		if(f[n][k+1][i]==0&&!flag)continue;
		flag=1;
		printf("%d",f[n][k+1][i]);
	}
	if(!flag)printf("0");
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}
int maaaa=ma();
int main(){;}