URAL_1013

    和URAL_1009的思路是一样的，只不过需要高精度，所以就直接用java写了。具体的一些思路可以参考我的URAL_1009的题解：。

    如果N再大一点的话，也可以用二分矩阵的方法优化dp的计算过程。

import java.math.BigInteger;import java.util.Scanner;public class Main {    static int N, K;    static BigInteger[][] f = new BigInteger[1810][2];    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        while(cin.hasNext())        {            N = cin.nextInt();            K = cin.nextInt();            solve();        }    }    static void solve()    {        int i;        f[1][0] = new BigInteger("0");        f[1][1] = BigInteger.valueOf(K - 1);        for(i = 2; i <= N; i ++)        {            f[i][0] = f[i - 1][1];            f[i][1] = f[i - 1][0].add(f[i - 1][1]).multiply(BigInteger.valueOf(K - 1));        }        System.out.println(f[N][0].add(f[N][1]));    }}