A box contains $N$ balls, each with an integer between $1$ and $M-1$ written on it.
For $i = 1, 2, \ldots, N$, the integer written on the $i$-th ball is $A_i$. While the box has two or more balls remaining, Takahashi will repeat the following. Print the maximum possible total score Takahashi will get.Problem Statement
Constraints
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 10 4 2 3 2
Sample Output 1
20
Consider the following scenario. Below, $X \bmod Y$ denotes the remainder when a non-negative integer $X$ is divided by a positive integer $Y$.
- Take the first and third balls from the box to score $(4^3 + 3^4) \bmod 10 = 5$ points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
- Take the third and fourth balls from the box to score $(3^2 + 2^3) \bmod 10 = 7$ points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
- Take the second and fourth balls from the box to score $(2^2 + 2^2) \bmod 10 = 8$ points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.
Here, Takahashi scores a total of $5 + 7 + 8 = 20$ points, which is the maximum possible value.
Sample Input 2
20 100 29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8
Sample Output 2
1733
做的时候硬是没看出这题，写个题解纪念一下。
如果我们把同选两个数 \(x,y\) 看作连一条边，那么最后会连出一棵树。此时从叶子节点选起，按照拓扑的方式往上走，选完后就把叶子节点删去，这就是一种按顺序取完这棵树的一种构造。那么这棵树的代价就是他的边权和。
反观这道题，其实就是一个最大生成树。暴力建边，跑kruskal就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,a[N],k,fa[N];
long long ans;
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int pow(int x,int y)
{
if(!y)
return 1;
int k=pow(x,y>>1);
if(y&1)
return 1LL*k*k%m*x%m;
return 1LL*k*k%m;
}
struct edge{
int u,v,w;
bool operator<(const edge&e)const{
return w>e.w;
}
}e[N*N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",a+i),fa[i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
e[++k]=(edge){i,j,(pow(a[i],a[j])+pow(a[j],a[i]))%m};
sort(e+1,e+k+1);
for(int i=1;i<=k;i++)
{
// printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);
if(find(e[i].u)!=find(e[i].v))
fa[find(e[i].u)]=find(e[i].v),ans+=e[i].w;
}
printf("%lld",ans);
}