Luogu

分析

考虑拆掉绝对值。对于一个数 $i$，如果它左右两边都比它小则其贡献为 $-2i$，如果一边比它小一边比它大则其贡献为 $0$，如果两边都比它大则其贡献为 $2i$。

考虑从小到大插入所有数。设 $f_{i, j, k, l}$ 表示插入了 $1 \sim i$，形成了 $j$ 个连续段，$1 \sim n$ 的贡献之和为 $k$，有 $l$ 个边界已经放了数的方案数。

这里我们认为两个连续段间有长度任意长的空位，且我们认为每段空位是没有区别的。

考虑转移，每次插入一个 $i$，有 $5$ 种情况：

• $i$ 一边是边界、一边是一个连续段：这样子连续段数不变，其贡献为 $i$，方案数为 $2 - l$。
• $i$ 一边是边界、一边是空位：这样子连续段数加 $1$，其贡献为 $-i$，方案数为 $2 - l$。
• $i$ 两边都是一个连续段：这样子连续段数减 $1$，其贡献为 $2i$，方案数为 $j - 1$。
• $i$ 一边是一个连续段、另一边是空位：这样子连续段数不变，其贡献为 $0$，方案数为 $2j - l$。
• $i$ 两边都是空位：这样子连续段数加 $1$，其贡献为 $-2i$，方案数为 $j + 1 - l$。

最后统计出总方案数再除以 $n!$ 即可。

然而要写高精度小数，不想写的话可以用 __float128。（但是全用 __float128 会 TLE 几个点，所以当 $k \leq 8$ 时得用 double）。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 100 + 10, M = 10000 + 10, L = 5000;

int n, m, k;
namespace Alice { double f[2][N][M][3]; }
namespace Cartelet { __float128 f[2][N][M][3]; }

template<typename T>
void print(T x) {
    printf("0."); x *= 10;
    for (int i = 1; i < k; ++i)
        printf("%d", (int)x), x = (x - (int)x) * 10;
    printf("%d\n",(int)(x + 0.5));
}

template<typename T>
void solve(T f[][N][M][3]) {
    f[0][0][L][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int now = i & 1, pre = now ^ 1;
        memset(f[now], 0, sizeof(f[now]));
        for (int j = 0; j < i; ++j)
            for (int k = 0; k <= L << 1; ++k)
                for (int l = 0; l <= 2; ++l) {
                    T w = f[pre][j][k][l];
                    if (j >= 2 && k + 2 * i <= L << 1) f[now][j - 1][k + 2 * i][l] += w * (j - 1);
                    if (j) f[now][j][k][l] += w * (2 * j - l);
                    if (k - 2 * i >= 0) f[now][j + 1][k - 2 * i][l] += w * (j + 1 - l);
                    if (l < 2 && j && k + i <= L << 1) f[now][j][k + i][l + 1] += w * (2 - l);
                    if (l < 2 && k - i >= 0) f[now][j + 1][k - i][l + 1] += w * (2 - l);
                }
    }
    T ans = 0;
    for (int i = m; i <= L; ++i) ans += f[n & 1][1][i + L][2];
    for (int i = 1; i <= n; ++i) ans /= i;
    print(ans);
}

int main() {
    n = read(), m = read(), k = read();
    if (k <= 8) solve(Alice::f);
    else solve(Cartelet::f);
    return 0;
}