1009的升级版 数据规模多了10倍 显然用高精
我写的是压4位的 好像不压也能过，但是压位的话输出一定要注意补0。。本人就是这里悲剧了。。
#include<stdio.h>
typedef struct gaojing
{
long l;
long a[1000];
}gaojing;
gaojing f[2000][2];
long n,k,i,x;
gaojing now;
gaojing add(gaojing *a,gaojing *b)
{
long ll,i;
gaojing c;
for (i=1;i<=1000;i++)
c.a[i]=0;
ll=a->l;
if (a->l<b->l)
ll=b->l;
for (i=1;i<=ll;i++)
c.a[i]=a->a[i]+b->a[i];
for (i=1;i<=ll-1;i++)
{
c.a[i+1]+=c.a[i]/1000;
c.a[i]%=1000;
}
c.l=ll;
if (c.a[ll+1]!=0)
c.l=ll+1;
return c;
}
gaojing mul(gaojing *a,long b)
{
long i;
gaojing c;
for (i=1;i<=1000;i++)
c.a[i]=0;
for (i=1;i<=a->l;i++)
c.a[i]+=a->a[i]*b;
for (i=1;i<=a->l+3;i++)
{
c.a[i+1]+=c.a[i]/1000;
c.a[i]%=1000;
}
for (i=a->l+3;i>=a->l;i--)
if (c.a[i]!=0)
{
c.l=i;
break;
}
return c;
}
int main()
{
scanf("%d %d",&n,&k);
f[1][0].l=1;f[1][0].a[1]=1;f[1][1].a[1]=k-1;f[1][1].l=1;
for (i=2;i<=n;i++)
{
f[i][0]=f[i-1][1];
now=add(&f[i-1][1],&f[i-1][0]);
f[i][1]=mul(&now,k-1);
}
printf("%d",f[n][1].a[f[n][1].l]);
for (i=f[n][1].l-1;i>=1;i--)
{
x=f[n][1].a[i];
if (x<100 && x>=10)
printf("0");
else if (x<10)
printf("00");
printf("%d",x);
}
}
posted on 2011-06-27 17:46
梦转千寻 阅读(68)
评论(0) 编辑 收藏 引用