HDU 5646 DZY Loves Partition

题目链接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5646

bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=680&pid=1002

DZY Loves Connecting

Accepts: 16 Submissions: 169

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

DZY有一棵nn个结点的无根树，结点按照1sim n1∼n标号。

DZY喜欢树上的连通集。一个连通集SS是由一些结点组成的集合，满足SS中任意两个结点u,vu,v能够用树上的路径连通，且路径上不经过SS之外的结点。显然，单独一个结点的集合也是连通集。

一个连通集的大小定义为它包含的结点个数，DZY想知道所有连通集的大小之和是多少。你能帮他数一数吗？

答案可能很大，请对10^9 + 7109+7取模后输出。

输入描述

第一行tt，表示有tt组数据。

接下来tt组数据。每组数据第11行一个数nn。第2sim n2∼n行中，第ii行包含一个数p_ipi，表示ii与p_ipi有边相连。(1le p_i le i-1,2le ile n1≤pi≤i−1,2≤i≤n)

(nge 1n≥1，所有数据中的nn之和不超过200000200000)

输出描述

每组数据输出一行答案，对10^9 + 7109+7取模。

输入样例

输出样例

Hint

第二个样例中，树的4条边分别为(1,2),(2,3),(2,4),(3,5)。所有连通集分别是{1},{2},{3},{4},{5},{1,2},{2,3},{2,4},{3,5},{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,2,3,4},{1,2,3,5},{2,3,4,5},{1,2,3,4,5}。

If you need a larger stack size,

please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

题解：

注：sum(a,k)表示以a为首项，项数为k的等差数列和（差值为1）

首先判断可行性:

如果sum(1,k)>n，那么明显无法将n划分成k个不同的数。

其次探究最优解的性质：

由于当1<=a<=b-2的时候有ab<(a+1)(b-1)，所以当k个数连续或只有一个长度为1的空隙的时候得到最优解。

求解最优值：

　　设由a开始的k个数为解，则有（a+a+k-1)*k/2==n，所以a>=(int)( ( (n*2.0/k)+1-k)/2)，经过调整可求得a',使得sum(a'-1,k) <=n<sum(a',k)。这样只要将数列sum(a',k)的前（sum(a',k)-n）项向左移一位即可求得最优解对应的数列。由sum(1,k)<=n得k<=sqrt(n),可对这个数列暴力求积。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #define SUM(a,k) ((a * 2 + k - 1)*k / 2)
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int mod = 1e9 + 7;
 8 
 9 LL n, k;
10 
11 int main() {
12     int tc;
13     scanf("%d", &tc);
14     while (tc--) {
15         scanf("%lld%lld", &n, &k);
16         if (n < (1 + k)*k / 2) {
17             printf("-1
");
18             continue;
19         }
20         LL a = (LL)((n * 2 * 1.0 / k + 1 - k) / 2);
21         while (SUM(a, k) <= n) a++;
22         LL adj = SUM(a, k) - n;
23         LL ans = 1;
24         for (int i = 0; i < k; i++) {
25             if (i < adj) {
26                 ans *= (a + i - 1);
27             }
28             else {
29                 ans *= (a + i);
30             }
31             ans %= mod;
32         }
33         printf("%lld
", ans);
34     }
35     return 0;
36 }

View Code