Calculate：简单计数 DP。
先考虑 \(\sum_{i = 1}^{p - 1}(a_{i + 1} - a_i)^2\) 的最大值怎么求。利用调整法可以得到结论：每次走当前未选的最大值、最小值交替选一定最优。还有另一种理解方式：注意到两数之差的平方很像欧几里得距离，所以把 \(a_i\) 变成点 \((a_i, a_i)\)，那么如果要让起点为 \(1\) 且走过的路径最长，则一定是 \(a_1\to a_n\to a_2\to a_{n - 1}\to a_3\to\cdots\) 的路径最优。
有了贪心结论，又因为是子序列，所以可以将原序列排序以方便计数。此时要我们统计的是这样反复横跳的路径的权值和。
容易设计出一个 DP：\(dp_i\) 表示以 \(i\) 为最左侧端点，且长度为偶数的路径个数；\(c_i\) 表示以 \(i\) 为最左侧端点，且长度为偶数的路径权值和。从左到右枚举到 \(i\) 时，转移如下：
- \(dp_{j}\overset{+}{\leftarrow} \sum_{k = j+1}^{i - 1}dp_k\)。
- \(c_j\overset{+}{\leftarrow} \sum_{k = j + 1}^{i - 1}c_k + \sum_{k = j+1}^{i - 1}dp_k\times (a_i - a_k)^2 + (\sum_{k = j+1}^{i - 1}dp_k)\times(a_i - a_j)^2\)。
直接转移是 \(O(n^3)\) 的，前缀和优化一下即可做到 \(O(n^2)\)。另一种做法是范德蒙德卷积加上一点数学推导，但是我不会。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 5005;
const ll mod = 998244353;
int n;
ll a[N], dp[N], c[N], ans;
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);for(int i = 1; i <= n; i++){ll smdp = 0, smc = 0, smdp2 = 0;for(int j = i - 1; j >= 1; j--){ll oridp = dp[j], oric = c[j];dp[j] = (dp[j] + smdp) % mod;c[j] = (c[j] + smc + smdp2 + smdp * (a[i] - a[j]) % mod * (a[i] - a[j]) % mod) % mod;smdp = (smdp + oridp) % mod;smdp2 = (smdp2 + oridp * (a[i] - a[j]) % mod * (a[i] - a[j]) % mod) % mod;smc = (smc + oric) % mod;dp[j] = (dp[j] + 1) % mod;c[j] = (c[j] + (a[i] - a[j]) * (a[i] - a[j]) % mod) % mod;}}for(int i = 1; i <= n; i++)ans = (ans + c[i]) % mod;cout << ans;return 0;
}