和Ural 1009一样，不过需要用到高精度，而且规模比之前大了不少，用了记忆化。
一开始测试数据的时候试了一个“10 170”的数据，发现结果很小，以为开100的数组应该够了。后来才发现我n和k弄反了！WA了一次！
给出“170 10”这个数据的结果，共170位。可以与自己的结果进行比对：
19140929114881653462
47604168411662739155
92368455809094944920
16732196087599513580
59650868133939742570
53930574840609094661
65965897483835868175
67975397667274771543
2612675930
以下是我的代码：
#include<iostream>
#include<string.h>
#define max_digit 177
#define maxn 187
using namespace std;
typedef struct
{
long n,s[max_digit];
}bign;
const bign nil={1,{-1}};
long n,k;
bign d[maxn][2];
void Add(bign &c,bign &a,bign &b)
{
memset(c.s,0,sizeof(c.s));
c.n=(a.n>b.n?a.n:b.n);
for(long i=0;i<c.n;i++)
{
c.s[i]+=a.s[i]+b.s[i];
if(c.s[i]>=10)
{
c.s[i]-=10;
c.s[i+1]++;
}
}
if(c.s[c.n]) c.n++;
}
void Mul(bign &c,long t,bign &a)
{
memset(c.s,0,sizeof(c.s));
c.n=a.n;
for(long i=0;i<c.n;i++)
c.s[i]=t*a.s[i];
for(long i=0;i<c.n;i++)
if(c.s[i]>=10)
{
c.s[i+1]+=c.s[i]/10;
c.s[i]%=10;
}
if(c.s[c.n]) c.n++;
}
void Print(bign &a)
{
for(long i=a.n-1;i>=0;i--)
cout<<a.s[i];
}
void dp(long i,long j)
{
if(d[i][j].n!=1||d[i][j].s[0]!=-1) return;
if(i==1)
{
dp(i+1,1);
Mul(d[i][j],k-1,d[i+1][1]);
return;
}
if(i==n)
{
if(j)
{d[i][j].n=1;d[i][j].s[0]=k;}
else
{d[i][j].n=1;d[i][j].s[0]=k-1;}
return;
}
if(j)
{
bign t;
dp(i+1,1);Mul(t,k-1,d[i+1][1]);
dp(i+1,0);Add(d[i][j],t,d[i+1][0]);
}
else
{
dp(i+1,1);
Mul(d[i][j],k-1,d[i+1][1]);
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n>>k;
for(long i=0;i<=n;i++)
d[i][0]=d[i][1]=nil;
dp(1,1);
Print(d[1][1]);
cout<<endl;
return 0;
}
posted on 2010-09-10 13:57
lee1r 阅读(387)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划