我是傻逼。很平凡的一个计数。但是不会啊。怎么会是呢。
考虑 Kruskal 求解 MST on Line 问题。我们可以想到统计边权 \(= a_i\) 的出现次数。
然后又可以容斥转化成统计边权 \(\le a_i\) 的出现次数,设其为 \(f_i\)。
考虑求 \(f_i\)。就相当于把 \(p\) 的 \(\le i\) 的位置集合 \(q\) 拿出来,求 \(\sum\limits_{j = 2}^i [q_j - q_{j - 1} \ge k]\)。
枚举 \(q_j - q_{j - 1} = t\),有方案数 \(\binom{n - t}{i - 1}\),并且不难发现每个 \(j\) 相互独立且方案数相等。
所以:
\[f_i = i! (n - i)! (i - 1) \sum\limits_{j = 1}^i \binom{n - j}{i - 1}
\]
时间复杂度 \(O(n^2)\)。
code
// Problem: C - MST on Line++
// Contest: AtCoder - AtCoder Regular Contest 167
// URL: https://atcoder.jp/contests/arc167/tasks/arc167_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5010;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, a[maxn], f[maxn], fac[maxn], ifac[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
f[i] = (f[i] + C(n - j, i - 1)) % mod;
}
f[i] = f[i] * fac[i] % mod * fac[n - i] % mod * (i - 1) % mod;
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + a[i] * (f[i] + mod - f[i - 1])) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Line 167atcoder regular contest 167 atcoder regular contest line atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 166 atcoder regular contest builder atcoder regular contest 164 subsegments atcoder regular contest