记录编号 293132 评测结果 AAAAAAAAAAAAAAA
题目名称 [POI 1997] n-k集合数 最终得分 100
用户昵称 Gravatar浮生随想 是否通过 通过
代码语言 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(){;}