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∑i=0Nd(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≤ 1015) The second line contains k integers,represent the set S，the elements in the set guarantee less than or equal to 1015. 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
Source
2019CCPC湖南全国邀请赛（广东省赛、江苏省赛）重现赛
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxx = 2e6+100; long long p; ll w[maxx]; ll a1[300]; ll a2[300]; int main(){ ios::sync_with_stdio(0); ll n,k,m; while(cin>>k>>m>>n>>p){ for(int i=1;i<=k;i++){ cin>>w[i]; } sort(w+1,w+1+k); if(m==1) cout<<0<<endl; else{ ll kk=1; for(int i=1;i<m;i++){ a1[i]=kk; a2[i]=a2[i-1]+a1[i]; kk*=n; } ll ans = 0; ll flag = a2[m-1]-1+kk; for(ll j=1;j<m;j++){ for(ll i=1;i<=a1[m-j]*n;i++){ ans = (ans%p+((w[flag--]%p)*(a2[j]%p)))%p; } } cout<<ans<<endl; } } return 0; }
