显然 \(\text{fun}(P)_{\max} = \frac{|P|(|P| + 1)}{2}\)。
考虑大力 dp，设 \(f_{i, j, k}\) 为 \(|P| = i\)，\(P_1 = j\)，\(\text{fun}(P) = k\) 的排列 \(P\) 的个数。此时 \(|L| = j - 1, |R| = i - j\)。转移枚举 \(L_1, R_1, \text{fun}(L), \text{fun}(R)\)，有：
\[f_{i, j, x + y + i} = \sum\limits_{k = 0}^i \sum\limits_{l = 0}^j \sum\limits_{x = 0}^{\frac{i(i - 1)}{2}} \sum\limits_{y = 0}^{\frac{(j - i)(j - i + 1)}{2}} f_{j - 1, k, x} \times f_{i - j, l, y} \times \binom{i - 1}{j - 1} \]答案即 \(\sum\limits_{i = 1}^n \sum\limits_{j = m}^{\frac{n(n + 1)}{2}} f_{n, i, j}\)。
\(\binom{i - 1}{j - 1}\) 的系数是已知 \(L, R\) 内元素的相对大小关系，它们组成 \(P_{2 \sim n}\) 的方案数。
发现转移最后一维出现了类似卷积的形式，考虑用多项式刻画转移。即设 \(F_{i, j}(x) = \sum\limits_{k} f_{i, j, k} x^k\)。那么：
\[F_{i, j}(x) = x^i \sum\limits_{k = 0}^i \sum\limits_{l = 0}^j \binom{i - 1}{j - 1} F_{j - 1, k}(x) F_{i - j, l}(x) \]令 \(G_i(x) = \sum\limits_{j = 1}^i F_{i, j}(x)\)，那么：
\[G_i(x) = x^i \sum\limits_{j = 1}^{i - 1} \binom{i - 1}{j - 1} G_{j - 1}(x) G_{i - j}(x) \]因为 \(\deg G_n(x) \le \frac{n(n + 1)}{2}\)，所以求出 \(G_n(x)\) 的 \(\frac{n(n + 1)}{2} + 1\) 个点的点值，就能拉插推得 \(G_n(x)\) 每一项的系数。
考虑如何点值转系数：
\[f(x) = \sum\limits_{i = 1}^n y_i \prod\limits_{j \ne i} \frac{x - x_j}{x_i - x_j} \]枚举 \(i\)，那么 \(\prod\limits_{j \ne i} \frac{1}{x_i - x_j}\) 是可以预处理阶乘及其逆元后 \(O(1)\) 算的（因为 \(x_i = i\)）。\(y_i\) 可以朴素 \(O(n^2)\) 计算。
考虑如何算 \(\prod\limits_{j \ne i} (x - x_j)\)。先算出 \(H(x) = \prod\limits_{i = 1}^n (x - x_i)\)，然后那个东西相当于 \(\frac{H(x)}{x - x_i}\)。做大除法即可。
时间复杂度 \(O(n^4)\)。虽然枚举带了个 \(\frac{1}{4}\) 常数但是需要不停取模所以跑得很慢。
code
// Problem: E. Jellyfish and Hack
// Contest: Codeforces - Codeforces Round 901 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1874/E
// Memory Limit: 512 MB
// Time Limit: 8000 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 = 210;
const int N = 40000;
const ll mod = 1000000007;
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, g[maxn], fac[maxn * maxn], ifac[maxn * maxn], pw[maxn], inv[maxn * maxn];
ll F[maxn * maxn], G[maxn * maxn], H[maxn * maxn], res[maxn * maxn];
inline void fix(ll &x) {
x = (x < 0 ? x + mod : x);
}
inline ll work(ll x) {
pw[0] = 1;
for (int i = 1; i <= n; ++i) {
pw[i] = pw[i - 1] * x % mod;
}
g[0] = 1;
for (int i = 1; i <= n; ++i) {
ll s = 0;
int k = 0;
for (int j = 0; j <= (i - 1) / 2; ++j) {
s += g[j] * g[i - 1 - j] * (1 + (j + j < i - 1));
if ((++k) == 4) {
s %= mod;
k = 0;
}
}
g[i] = s % mod * pw[i] % mod * inv[i] % mod;
}
return g[n] * fac[n] % mod;
}
void solve() {
scanf("%lld%lld", &n, &m);
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;
}
inv[1] = 1;
for (int i = 2; i <= N; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
F[0] = 1;
for (int i = 1; i <= n * (n + 1) / 2 + 1; ++i) {
for (int j = i; ~j; --j) {
F[j] = (j ? F[j - 1] : 0) - F[j] * i;
if (i & 1) {
F[j] %= mod;
fix(F[j]);
}
}
}
for (int i = 1; i <= n * (n + 1) / 2 + 1; ++i) {
G[n * (n + 1) / 2 + 1] = F[n * (n + 1) / 2 + 1];
for (int j = n * (n + 1) / 2; ~j; --j) {
H[j] = G[j + 1];
G[j] = (F[j] + H[j] * i) % mod;
}
ll p = work(i);
p = p * ifac[i - 1] % mod;
p = p * ifac[n * (n + 1) / 2 + 1 - i] % mod;
if ((n * (n + 1) / 2 + 1 - i) & 1) {
p = (mod - p) % mod;
}
bool fl = (i % 9 == 0);
for (int j = 0; j <= n * (n + 1) / 2; ++j) {
res[j] += H[j] * p;
if (fl) {
res[j] %= mod;
}
}
}
ll ans = 0;
for (int i = m; i <= n * (n + 1) / 2; ++i) {
ans = (ans + res[i]) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
由于本人被 CF 32 位机整破防了，所以代码有点卡常。
标签：1874E,frac,limits,sum,CodeForces,typedef,maxn,Hack,ll From： https://www.cnblogs.com/zltzlt-blog/p/18069558