赛时过程
ABCDE 五题，ACM / ICPC 赛制，线上赛，两个半小时。
A 题签到，手画了一棵树就瞬间 AC。
开 B，感觉是神仙题，这时看到数论神仙 Leasier 已经 A 了 D，于是妄想先切 D 题。
开 D，显然数论，口胡了一下结果样例都没过，就爬回去看 B。
回到 B 题，感觉不是 dp 就是组合，dp 方程推不出来，然后就想组合数解法，就 A 了。
C 题一眼差分，然后画了几个数组，也 A 了。
D 题忽然想到 gcd \gcd gcd 的另一种分解质因数的求法，愉快地 AC。
E 题是 smg，爪巴了。
最后…
我 tmd 为什么是 rk1？？
赛后总结
提交次数还是多了，以后最好一次性 AC。
赛后题解
A 题是 sb 题，就不说了。
B 题：
- 在 [ 1 , n ] [1,n] [1,n] 中选数 m m m 次，可重复。
- 设选出的序列排序后为 a 1 , a 2 , . . . , a m a_1,a_2,...,a_m a1,a2,...,am。
- 定义序列的贡献为 max { a 1 , a 2 , . . . , a m } − min { a 1 , a 2 , . . . , a m } \max\{a_1,a_2,...,a_m\}-\min\{a_1,a_2,...,a_m\} max{a1,a2,...,am}−min{a1,a2,...,am}。
- 求出所有本质不同的序列的贡献和，答案对 998244353 998244353 998244353 取模。
现在假设已经选出了一个序列中的 max \max max 和 min \min min，那么显然剩下 m − 2 m-2 m−2 个数就只能在 [ min , max ] [\min,\max] [min,max] 之间选出，由于是可重复，所以套用可重复组合数的公式即可，剩下 m − 2 m-2 m−2 个数的方案数为 C max − min + 1 + m − 2 − 1 m − 2 C_{\max-\min+1+m-2-1}^{m-2} Cmax−min+1+m−2−1m−2，化简得 C max − min + m − 2 m − 2 C_{\max-\min+m-2}^{m-2} Cmax−min+m−2m−2，算这个只需要预处理阶乘然后用逆元来算即可。
接下来看 max \max max 和 min \min min 要怎么枚举，显然二重循环暴力是不可行的，那么观察上式发现只用得着 max − min \max-\min max−min，于是只用枚举 max − min \max-\min max−min，对于每个 max − min \max-\min max−min 有 n − ( max − min + 1 ) + 1 n-(\max-\min+1)+1 n−(max−min+1)+1 种选法，化简得 n − ( max − min ) n-(\max-\min) n−(max−min)，而贡献即为 max − min \max-\min max−min。
所以最终答案就是：
∑
i
=
1
n
−
1
C
i
+
m
−
2
m
−
2
×
(
n
−
i
)
×
i
\sum_{i=1}^{n-1}C_{i+m-2}^{m-2}\times(n-i)\times i
i=1∑n−1Ci+m−2m−2×(n−i)×i
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll fac[1000005];
inline void init_fac (int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
}
inline ll quickPow (ll a, ll k, ll p) {
ll res = 1;
a %= p;
while (k) {
if (k & 1)
res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
inline ll inv (ll x, ll p) {
return quickPow(x, p - 2, p);
}
inline ll getC (int n, int m, ll p) {
if (n < m || n < 0 || m < 0)
return 0;
if (n == m || m == 0)
return 1;
return fac[n] * inv(fac[m] * fac[n - m] % p, p) % p;
}
int main () {
int n, m;
scanf("%d %d", &n, &m);
init_fac(1e6);
ll ans = 0;
for (int i = 1; i < n; i++)
ans = (ans + 1ll * (n - i) * i % mod * getC(i + m - 2, m - 2, mod) % mod) % mod;
printf("%lld", ans);
return 0;
}
其他的先咕着。