首页 > 其他 > 详细

ural 1012. K-based Numbers. Version 2(大数dp)

时间:2014-04-17 01:14:59      阅读:569      评论:0      收藏:0      [点我收藏+]

和1009相同,只是n达到了180位,可以模拟大数加和大数乘,这里用的java中的大数。

bubuko.com,布布扣
 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner cin = new Scanner(System.in);
 6         while (cin.hasNext()) {
 7             int n = cin.nextInt();
 8             int k = cin.nextInt();
 9             BigInteger[][] dp = new BigInteger[200][2];
10             dp[1][0] = BigInteger.ZERO;
11             dp[1][1] = BigInteger.valueOf(k - 1);
12             for (int i = 2; i <= n; i++) {
13                 dp[i][0] = dp[i - 1][1];
14                 dp[i][1] = dp[i - 1][0].add(dp[i - 1][1]).multiply(
15                         BigInteger.valueOf(k - 1));
16 
17             }
18 
19             BigInteger ans = dp[n][0].add(dp[n][1]);
20             System.out.println(ans);
21         }
22 
23     }
24 }
View Code

 

ural 1012. K-based Numbers. Version 2(大数dp),布布扣,bubuko.com

ural 1012. K-based Numbers. Version 2(大数dp)

原文:http://www.cnblogs.com/lahblogs/p/3669354.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!