首页 > 代码库 > SGU 407 Number of Paths in the Empire dp+java大数
SGU 407 Number of Paths in the Empire dp+java大数
SGU 407
407. Number of Paths in the Empire
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
Memory limit: 65536 kilobytes
input: standard
output: standard
output: standard
During the period of Tsam dynasty ruling people rarely fought against each other and their neighbours, because they just could not afford themselves such a waste of time. The matter for it is that they were entirely absorbed with solving various problems which were connected with trade, craft, agriculture and other spheres of human activity. In a wide list of problems the ones of tax collection stand out. As one of such problems was posed by Emperor himself, it was of great importance. The problem was to count the number of different paths consisting of exactly m roads. Every path should have started and ended in the capital of Empire. Paths were supposed to cover the same towns and roads any times, moreover they could cover the capital several times. Now you are to solve this problem given information about Empire: there were n country towns situated at the foot of a hill, they formed a circle at the bottom, and the capital was on the top of the hill. The capital was connected to all other towns, and each country town was also connected to other two neighbouring country towns both to the left and to the right. Pic. 1 Empire comprising the capital (index 0) and four country towns (indices 1 — 4).
Input
The only line of input file contains two integers n and m (3 ≤ n ≤ 1000, 0 ≤ m ≤ 5000). Output
Output the answer without leading zeros. Example(s)
sample input | sample output |
4 3 | 8 |
sample input | sample output |
3 4 | 21 |
Commentary to the first sample test. There are 8 paths in the Empire. 0-1-2-0, 0-2-3-0, 0-3-4-0, 0-4-1-0, 0-2-1-0, 0-3-2-0, 0-4-3-0, 0-1-4-0.
dp方程还是很好写的,,然后来个大数,本地跑不出极限数据一直没交,实在无解了才交了一发,居然过了。。
==
import java.io.*; import java.util.*; import java.math.*; public class Solution { BigInteger[][] dp = new BigInteger[5005][2]; public void work() { int n, m; n = cin.nextInt(); m = cin.nextInt(); dp[0][0] = BigInteger.ONE; dp[0][1] = BigInteger.ZERO; for(int i = 1; i <= m ; i++) { dp[i][0] = dp[i-1][1]; BigInteger tmp = dp[i-1][0].multiply(BigInteger.valueOf(n)); dp[i][1] = tmp.add(dp[i-1][1].multiply(BigInteger.valueOf(2))); } out.println(dp[m][0]); //out.println('*'); out.close(); } Solution() { cin = new Scanner(System.in); out = new PrintWriter(System.out); } public static void main(String[] args) { Solution e = new Solution(); e.work(); } public Scanner cin; public PrintWriter out; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。