记录编号 |
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(){;}