来自"NOCOW"

#include<stdio.h>
#include<string.h>
 
const int max=1000000;
int n,k,i;
struct bignum
{
    int v[400];
    bignum()
    {
        memset(v,0,sizeof(v));
        v[0]=1;
    }
}f[181];
 
void plus()
{
    bignum v1;
    int len,j,k;
    if(f[i-1].v[0]>f[i-2].v[0])
        len=f[i-1].v[0];
    else
        len=f[i-2].v[0];
    for(j=1;j<=len;j++)
       v1.v[j]=f[i-1].v[j]+f[i-2].v[j];
    int tmp=0;
    for(j=1;j<=len;j++)
    {
        v1.v[j+1]+=(v1.v[j]/max);
        v1.v[j]=v1.v[j]%max;
    }
    j-=1;
    while(v1.v[j+1]>0)
    {
        j+=1;
        v1.v[j+1]=v1.v[j]/max;
        v1.v[j]=v1.v[j]%max;
    }
    v1.v[0]=j;
    f[i]=v1;
}
 
void mul()
{
    bignum v1;
    v1=f[i];
    int j;
    for(j=1;j<=v1.v[0];j++)
        v1.v[j]*=k;
    int tmp=0,len=v1.v[0];
    for(j=1;j<=len;j++)
    {
        v1.v[j+1]+=(v1.v[j]/max);
        v1.v[j]=v1.v[j]%max;
    }
    j-=1;
    while(v1.v[j+1]>0)
    {
        j+=1;
        v1.v[j+1]=v1.v[j]/max;
        v1.v[j]=v1.v[j]%max;
    }
    v1.v[0]=j;
    f[i]=v1;
}
 
void draw()
{
    if(f[n].v[i]==0)
    {
        printf("0000000");
    }
    else
    {
        int tmp=f[n].v[i];
        while(tmp<max/10)
        {
            tmp*=10;
            printf("0");
        }
        printf("%d",f[n].v[i]);
    }
}
 
int main()
{
    scanf("%d",&n);
    scanf("%d",&k);
    k-=1;
    f[0].v[1]=1;
    f[1].v[1]=k;
    for(i=2;i<=n;i++)
    {
        plus();
        mul();
    }
    printf("%d",f[n].v[f[n].v[0]]);
    int len=f[n].v[0]-1;
    for(i=len;i>0;i--)
        draw();
    return 0;
}

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.lang.*;
public class Main {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner cin = new Scanner(System.in);
        int n , k;
        while(cin.hasNext()){
            n = cin.nextInt();
            k = cin.nextInt();
            BigInteger []a = new BigInteger[n+2];
            a[0] = BigInteger.ONE;
            a[1] = BigInteger.valueOf(k-1);
            for(int i = 2 ; i < n+2 ; i++){
                a[i] = a[i-1].add(a[i-2]);
                a[i] = a[i].multiply(BigInteger.valueOf(k-1));
            }
            System.out.println(a[n]);
         }
    }
}

[编辑] 和1009一模一样的题目,题解可参照那道题,只是需要高精度

program cao;
const
  maxn=500;
 
var
  a,b,c:array[0..maxn+1] of longint;
  d,e,f,g,h,i,j,k,l,n,m,p,q:longint;
  s:string;
 
begin
  read(n,k);
  if n<2 then
  begin
    if n=0 then writeln(1);
    if n=1 then writeln(k-1);
    halt;
  end;
  a[maxn]:=1;
  b[maxn]:=k-1;
  for i:=2 to n do
  begin
    for j:=1 to maxn do
      c[j]:=(a[j]+b[j])*(k-1);
    for j:=maxn downto 1 do
    begin
      c[j]:=c[j]+c[j+1] div 1000000;
      c[j+1]:=c[j+1] mod 1000000;
    end;
    a:=b;
    b:=c;
  end;
  for i:=1 to maxn do
    if c[i]<>0 then break;
  write(c[i]);
  for i:=i+1 to maxn do
  begin
    str(c[i],s);
    while length(s)<6 do insert(‘0′,s,1);
    write(s);
  end;
  writeln;
end.

[编辑] 贡献一个C++高精度类

#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
class Bigint
{
	public:
	static const int sa = 2000;
	int * da;
	~Bigint();
	Bigint(const int n);
	Bigint(const Bigint &a);
	Bigint operator=(const int n);
	Bigint operator=(const Bigint &a);
	Bigint operator+(const Bigint &b);
	Bigint operator*(const int n);
	friend ostream &operator<<(ostream &s, Bigint &a);
	friend istream &operator>>(istream &s, const Bigint &a);
};
 
Bigint::~Bigint()
{
	delete [] da;
}
 
Bigint::Bigint(const int n = 0)
{
	da = new int[sa];
	memset(da, 0, sizeof(int) * sa);
	da[1] = n;
	int i;
	for(i = 1 ; da[i] ; i++)
	{
		da[i + 1] += da[i] / 10;
		da[i] %= 10;
	}
	da[0] = i - 1;
}
 
Bigint::Bigint(const Bigint &a)
{
	da = new int[sa];
	memcpy(da, a.da, sizeof(int) * sa);
}
 
Bigint Bigint::operator=(const Bigint &a)
{
	memcpy(da, a.da, sizeof(int) * sa);
	return *this;
}
 
Bigint Bigint::operator=(const int n)
{
	Bigint c(n);
	*this = c;
	return *this;
}
 
Bigint Bigint::operator+(const Bigint &b)
{
	Bigint &a = *this;
	Bigint c;
	c.da[0] = max(a.da[0], b.da[0]);
	int i;
	for(i = 1 ; i <= c.da[0] ; i++)
	{
		c.da[i] += a.da[i] + b.da[i];
		c.da[i + 1] += c.da[i] / 10;
		c.da[i] %= 10;
	}
	for(; c.da[i] ; i++)
	{
		c.da[i + 1] += c.da[i] / 10;
		c.da[i] %= 10;
	}
	c.da[0] = i - 1;
	while(c.da[c.da[0]] == 0 && c.da[0] > 1) c.da[0]--;
	return c;
}
 
Bigint Bigint::operator*(const int n)
{
	Bigint &a = *this;
	Bigint c;
	int i;
	for(i = 1 ; i <= a.da[0] ; i++)
	{
		c.da[i] += a.da[i] * n;
		c.da[i + 1] += c.da[i] / 10;
		c.da[i] %= 10;
	}
	for(; c.da[i] ; i++)
	{
		c.da[i + 1] += c.da[i] / 10;
		c.da[i] %= 10;
	}
	c.da[0] = i - 1;
	while(c.da[c.da[0]] == 0 && c.da[0] > 1) c.da[0]--;
	return c;
}
 
ostream &operator<<(ostream &s, Bigint &a)
{
	int i, l;
	l = a.da[0];
	for(i = l ; i >= 1 ; i--)
		s << a.da[i];
	return s;
}
 
istream &operator>>(istream &s, Bigint &a)
{
	int k, i;
	s >> k;
	Bigint c(k);
	a = c;
	return s;
}
 
Bigint f[3];
 
void work()
{
	int n, k;
	cin >> n >> k;
	f[0] = 1;
	f[1] = k - 1;
	for(int i = 2 ; i <= n ; i++)
		f[i % 3] = (f[(i - 1) % 3] + f[(i - 2) % 3]) * (k - 1);
	cout << f[n % 3] << endl;
}
 
int main()
{
	work();
	return 0;
}