和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 閱讀(404)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃