ASC(22)H(大数+推公式)
High Speed Trains
Time Limit:?4000/2000MS (Java/Others)
Memory Limit:?128000/64000KB (Java/Others)
Submit
Statistic
Next Problem
Problem Description? ? ? The kingdom of Flatland has n cities. Recently the king of Flatland visited Japan and was amazed by?high speed trains Shinkansens going all around the country. Therefore he decided to build the system of?high speed trains in Flatland. ? ? ? Each high speed train line will be bidirectional and connect exactly two different cities of Flatland.?Although there is actually no need of high speed trains in Flatland,the king ordered that there must be?at least one high speed train line from each city of Flatland. Input
? ? ? The input file contains one integer number n (2 ≤ n ≤ 100)
Output
? ? ? Output one integer number — the number of different train systems that can be arranged in Flatland.
Sample Input4 Sample Output41
题意:给出图的点数n,要求的是由这n个点可以构成多少种图,要满足每个点至少有一条边相连,两点之间最多一条边,图可以不连通
思路:推公式题
? ? ? ? ? ? dp[n] = dp[n-1] * ( 2^(n-1) - 1 ) + C( n-1,1 ) * 2^(n-2) * dp[n-2] +?C( n-1,2 ) * 2^(n-3) * dp[n-3] + ...... +?C( n-1,n-3 ) * 2^( 2 ) * dp[ 2 ] + 1
? ? ? ? ? ? 要用大数
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |