HDUOJ 6533 Build Tree

HDUOJ 6533 Build Tree

题目链接

Problem Description

You need to construct a full n-ary tree(n叉树) with m layers.All the edges in this tree have a weight.But this weight cannot be chosen arbitrarily you can only choose from set S，the size of S is k，each element in the set can only be used once.Node 0 is the root of tree.

We use d(i) for the distance from root to node i.Our goal is to minimize the following expression:
$$min\sum _{i=0}^{N}d(i)$$

Please find the minimum value of this expression and output it.Because it may be a big number,you should output the answer modul p.

Input

The input file contains 2 lines.

The first line contains 4 integers,these respectively is k,m,n,p。(2 ≤ k ≤200000,2 ≤ p≤ 1e15)

The second line contains k integers,represent the set S，the elements in the set guarantee less than or equal to 1e15.

We guarantee that k is greater than or equal to the number of edges.

Output

The output file contains an integer.represent the answer.

Sample Input

5 2 3 10
1 2 3 4 5

Sample Output

6

思维题~
下面讲一下我的思路，首先可以算出 $m$ 层满 $n$ 二叉树的边数:
$num=n^1+n^2+?+n^{m?1}=\frac{n^m?n}{n?1}$
很容易发现越上层的边用到的次数越多，所以我们要对数组排序，将权值最小的放上层，这样才能使答案最少，因为对同一层边的使用次数是相同的，所以我们可以计算出前缀和，这样对每一层的计算就等于该层所有边权值的前缀和乘上调用次数，下面只需要考虑每一层的调用次数即可，我们就拿 $n=2,m=4$ 举例：

  /  \   ------>调用7=1+2+4次/\  /\  ------>调用3=1+2次
/\/\/\/\ ------>调用1=1次

很容易发现对第 $i$ 层，调用次数即为 $n^1+n^2+?+n^{m?i?1}$ 次，就是一个简单的等比数列求和，答案就是每一层加起来即可，注意要多组输入，AC代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n,m,k,p,a[N],sum[N];
ll Pow(ll n,ll m){
    ll ans=1;while(m--) ans=(ans*n)%p;return ans;
}ll Sum(ll n,ll m){
    ll ans=0;for(ll i=0;i<m;i++) ans=(ans+Pow(n,i))%p;return ans;
}int main() {
    while(~scanf("%lld%lld%lld%lld",&k,&m,&n,&p)) {
    memset(sum,0,sizeof(sum));ll num=(Pow(n,m)- n)/(n-1),ans=0;for(ll i=1;i<=k;i++) scanf("%lld",&a[i]);sort(a+1,a+1+k);for(ll i=1;i<=num;i++) sum[i]=(a[i]+sum[i-1])%p;for(ll i=1,j=m-1;i<=num&&j>0;i+=Pow(n,m-j),j--) {
    ans=(ans + Sum(n,j)*(sum[i+Pow(n,m-j)- 1]-sum[i - 1])%p)%p;if(ans<0) ans=(p-(-ans)%p)%p;}printf("%lld\n",ans);}return 0;
}