题目大意
一个长度为 $n$ 的排列 $\{P_i\}$ 的价值为
$$\sum_{i=2}^n|P_i-P_{i-1}| $$
给定 $n,m,k$ ，求出长度为 $n$ ，价值不小于 $m$ 的排列的频率，保留小数点后 $k$ 位。
$n\le 100$ .
思路
不难想到用 DP 实现。暂且先考虑设 $f_{i,j}$ 表示填了 $i$ 个位置，且价值达到 $j$ 的方案数。然而这样不能维护转移，不好维护选了哪些数。
实际上，我们只关心数字的相对大小而不关心具体选了哪些数，这或许能够成为突破口。因而我们把状态设为一个数集 $S$ ，表示选了的数。转移时，相对大小为主元，故考虑不断加入更大（或更小，它们地位相同，以更大为例）的数，而且是逐个连续加入，那么以 $1$ 开始从小到大加入即可。于是设 $f_{i,j}$ 表示选择了前 $i$ 个数，且价值达到 $j$ 的方案数。
继续考虑转移。这个状态仍然不好维护价值变化。试把选择了的 $i-1$ 个数分散到各个位置，再加入 $i$ 。发现 $i-1$ 个数形成若干个块，而围绕这些块，转移有几种情况：
- $i$ 新开一块（可以和边界连或否）；
- $i$ 一端连旧有的块，一端连空白或边界；
- $i$ 与两个旧块相连，它们合并。
由此我们可以设出最终的状态： $f_{i,j,k,l}$ 表示加入了前 $i$ 个数，存在 $j$ 个块，价值达到 $k$ ，且占了 $l$ 个端点的方案数。
根据上面的分列，不难推出转移方程。
时间复杂度 $\mathcal{O}(n^4)$ 。
代码
思路锻炼很好，但代码实现有点难受，不知道考察的目的。高精度常数好大，压位也不能解决，很痛苦，学习了 double 和 __float128 切换的实现。
滚动数组优化空间。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110, K = 10010, mod = 998244353;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace db{long double f[2][N][K][3];}
namespace ft{__float128 f[2][N][K][3];}
namespace Main {
int n, m, k;
/*
const int base = 1e7;
struct __int200{
const static int M = 11;
int d[M];
__int200() { memset(d, 0, sizeof d); }
__int200(int x) { for (memset(d, 0, sizeof d); x; d[++d[0]] = x % base, x /= base); }
};
__int200 operator + (__int200 a, __int200 b) {
int r = 0; a.d[0] = max(a.d[0], b.d[0]);
for (int i = 1; i <= max(1, a.d[0]); ++i) {
int x = a.d[i] + b.d[i] + r;
a.d[i] = x % base;
r = x / base;
a.d[0] += (i == a.d[0] && r);
}
return a;
}
void operator += (__int200 &a, __int200 b) {
a = a + b;
}
// __int200 operator * (__int200 a, int b) {
// int r = 0;
// for (int i = 1; i <= a.d[0]; ++i) {
// int m = a.d[i] * b + r;
// a.d[i] = m % 10;
// r = m / 10;
// a.d[0] += (i >= a.d[0] && r);
// }
// return a;
// }
__int200 operator * (__int200 a, __int200 b) {
__int200 c(0);
if (!a.d[0] || !b.d[0]) return c;
c.d[0] = a.d[0] + b.d[0];
for (int i = 1; i <= a.d[0]; ++i)
for (int j = 1; j <= b.d[0]; ++j)
c.d[i + j - 1] += a.d[i] * b.d[j];
for (int i = 1; i <= c.d[0]; ++i) {
c.d[i + 1] += c.d[i] / base;
c.d[0] += (i == c.d[0] && c.d[i] >= base);
c.d[i] %= base;
}
for (; !c.d[c.d[0]] && c.d[0] >= 0; c.d[0]--);
return c;
}
__int200 operator / (__int200 a, int b) {
__int200 c;
for (int i = a.d[0]; i; --i) {
int t = a.d[i] + a.d[i + 1] * base;
c.d[i] = t / b;
a.d[i] = t % b;
a.d[i + 1] = 0;
c.d[i] += (i == 0 && a.d[i] >= b / 2);
c.d[0] = (!c.d[0] && c.d[i])? i: c.d[0];
}
return c;
}
*/
const int zer = K / 2;
template < class T >
void write (T x) {
if(x + 1e-14 >= 1)cout << "1." << string(k, '0') << endl;
else {
cout << "0.", x *= 10;
for(int i = 1; i <= k; ++i)cout << (int)(x + (i == k ? 0.5 : 0)), x = (x - (int)x) * 10;
}
}
template < class T >
void solve(T f[][N][K][3]){
f[0][0][zer][0] = 1;
for (int i = 1; i <= n; i++) {
int now = i & 1;
memset(f[now], 0, sizeof f[now]);
for (int j = 0; j < i; ++j)
for (int k = 0; k < K; ++k)
for (int l = 0; l < 3; ++l)
if(f[now ^ 1][j][k][l]) {
if (j) f[now][j][k][l] += f[now ^ 1][j][k][l] * (j * 2 - l) / i;
if (k - 2 * i >= 0) f[now][j + 1][k - 2 * i][l] += f[now ^ 1][j][k][l] * (j + 1 - l) / i;
if (j >= 2 && k + 2 * i < K) f[now][j - 1][k + 2 * i][l] += f[now ^ 1][j][k][l] * (j - 1) / i;
if (l < 2) {
if (k - i >= 0) f[now][j + 1][k - i][l + 1] += f[now ^ 1][j][k][l] * (2 - l) / i;
if (j && k + i < K) f[now][j][k + i][l + 1] += f[now ^ 1][j][k][l] * (2 - l) / i;
}
}
}
T ans(0);
for (int i = m; i <= (n + 1) * n / 2; ++i) ans += f[n & 1][1][i + zer][2];
write(ans);
}
int main () {
n = read(), m = read(), k = read();
if (k <= 8) solve(db::f);
else solve(ft::f);
return 0;
}
}
int main () {
string str = "";
// freopen((str + ".in").c_str(), "r", stdin);
// freopen((str + ".out").c_str(), "w", stdout);
Main::main();
return 0;
}
EOF
P2612