题目描述

难度分:$1604$

输入$n(2 \leq n \leq 500)$，$m(2 \leq m \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq m-1)$。

重复如下操作$n-1$次：

• 选择$a$中的两个数$x$和$y$，得到$(x^y+y^x) \% m$分，然后从$a$中删除$x$或者$y$。

输出总得分的最大值。

输入样例$1$

4 10
4 2 3 2

输出样例$1$

20

输入样例$2$

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

输出样例$2$

1733

算法

最小生成树

这个题隐藏很深，其实这个操作就相当于每次在$n$个孤立点中找到两个点$u$和$v$，每次累加上这两个点带来的收益$(a[u]^{a[v]}+a[v]^{a[u]}) \% m$。然后这两个点其中的一个就废掉了，假设废掉了$u$，接下来如果再选到$v$点，那就是累加$v$与它其他邻居的收益点。

这个过程就像是每次将两个点用边连接起来，执行$n-1$次所有的$n$个孤立点就合并成了一个连通图。完全就是$Kruskal$算法求最小生成树的过程，而题目要求答案最大化，那就将所有边权取相反数。运行$Kruskal$算法的时候，将原来加边权的操作改为减边权，这样得到的就是我们本题要求的最大值。

复杂度分析

时间复杂度

每对点之间都可以连边，因此边集的大小为$O(n^2)$，将所有边按照边权排序的时间复杂度为$O(n^2log_2n)$。接下来运行$Kruskal$算法需要遍历$n^2$条边，每条边需要进行并查集的合并操作，合并操作的时间复杂度为$O(logn)$（该对数的底数不是$2$，其实这个过程的时间复杂度很低，可以看成是一个稍大的常数），将所有孤立点变成一个连通图的时间复杂度为$O(n^2logn)$。整个算法的时间复杂度为$O(n^2(log_2n+logn))$。

空间复杂度

空间消耗分为两个部分，一个是并查集$O(n)$的空间，另一个就是边集数组的消耗$O(n^2)$。显然瓶颈在后者，整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 501;
int n, m, a[N], p[N];

int fast_power(int a, int k) {
    int res = 1 % m;
    while(k) {
        if(k&1) res = (LL)res * a % m;
        a = (LL)a * a % m;
        k >>= 1;
    }
    return res;
}

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p[i] = i;
    }
    vector<array<int, 3>> edges;
    for(int i = 1; i < n; i++) {
        for(int j = i + 1; j <= n; j++) {
            edges.push_back({-((fast_power(a[i], a[j]) + fast_power(a[j], a[i])) % m), i, j});
        }
    }
    sort(edges.begin(), edges.end());
    LL ans = 0;
    for(auto&edge: edges) {
        int u = edge[1], v = edge[2], w = edge[0];
        if(find(u) != find(v)) {
            ans -= w;
            merge(u, v);
        }
    }
    printf("%lld\n", ans);
    return 0;
}