很好的组合数学题。
考虑以任意一个点为基准计算方案数，最终答案乘上 \(\dfrac L n\) 即可。
枚举点两两之间最短路径 \(\le d\)，计算方案数，剩下的 \(n - 1\) 个点都应该至多在基准点的左 \(d\) 个和右 \(d\) 个点的位置。
显然左右 \(d\) 个位置内部的距离都不超过 \(d\)，只需要判定两边结合起来是否合法。
考虑选择了左边的一个点，右边就会有一段点不能选；右边同理。一个神奇的方法：把左边的点旋转到限制的一段点的第一个位置，并视为黑点，右边的点视为白点。那么条件相当于：所有点不重合，并且黑点后面固定长度的一段点不能选白点，白点前面固定长度的一段点不能选黑点。
令基准点为白点。枚举黑转白的次数 \(i\)，设不能选的一段点长度为 \(t\)，那么选点的方案数为 \(\dbinom {d - i\cdot t} {n - 1}\)。再考虑黑白染色，相当于分成 \(2(i + 1)\) 段，除了第一段和最后一段，其他段非空的方案数，插板法得出方案数为 \(\dbinom {n} {2i + 1}\)。
所有 \(i\) 的总和为调和级数级别的，可以通过。
- 启示：基准点 trick；调整模型，观察组合方案。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll maxn = 2e6 + 10, mod = 998244353;
void rd(ll &x) {
char ch;
while(!isdigit(ch = getchar())) ;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
} ll n, m, c[maxn], ans, fac[maxn], ifac[maxn];
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = s * a %mod;
a = a * a %mod, b >>= 1;
} return s;
}
ll C(ll a, ll b) { return a < b || b < 0? 0 : fac[a] * ifac[b] %mod * ifac[a - b] %mod; }
int main() {
rd(m), rd(n);
fac[0] = 1;
for(ll i = 1; i <= n + m; i++) fac[i] = fac[i - 1] * i %mod;
ifac[n + m] = power(fac[n + m]);
for(ll i = n + m; i; i--) ifac[i - 1] = ifac[i] * i %mod;
for(ll d = 1; 2 * d <= m; d++) {
ll t = m - 2 * d - 1;
if(t <= 0) c[d] = C(m - 1, n - 1);
else
for(ll i = 0; i * t <= d; i++)
c[d] = (c[d] + C(d - i * (t - 1), n - 1) *
C(n, 2 * i + 1)) %mod;
ans = (ans + (c[d] + mod - c[d - 1]) * d) %mod;
} printf("%lld", ans * m %mod * power(n) %mod);
return 0;
}