题解：P7986 [USACO21DEC] HILO P

· · 题解

独立切了，暴力炸金方法。

令 x=n-x，可以转换成计数 LOHI。考虑某个贡献对 a_i=p, a_j=q, i<j, p<q，剩下的数分成三类。第一类 [1,p-1] 随便放，第二类 [p+1,q-1] 显然只能放到 j 后，第三类 [q+1,n] 不能在 [i+1,j-1] 形成前缀最大值。第三类可以这么刻画：令第三类点在 j-1 前的最小值为 k，枚举并钦定 k 出现在 [1,i-1]。所以得到五次方式子，并开始暴力化简（其实还有一个余项是 i=1，但是这里不写待会儿分开写）：

\begin{aligned} &\sum_{p=1}^{x}\sum_{q=x+1}^{N}\sum_{i=2}^{N-1}\sum_{j=i+1}^{N}\sum_{k=q+1}^{N}(i-1)A(n-j, q-p-1)A(n-j-(q-p-1), k-1-q)A(n-k+(p-1),n-k)(p-1)!\\ =&\sum_{p=1}^{x}\sum_{q=x+1}^{N}\sum_{i=2}^{N-1}\sum_{j=i+1}^{\min(N,N-q+p+1)}\sum_{k=q+1}^{\min(N,N-j+p+2)}(i-1)\frac{(N-j)!}{(N-j-q+p+1)!}\frac{(N-j-q+p+1)!}{(N-j-k+p+2)!}\frac{(N-k+p-1)!}{(p-1)!}(p-1)!\\ =&\sum_{p=1}^{x}\sum_{q=x+1}^{N}\sum_{j=3}^{\min(N,N-q+p+1)}\sum_{k=q+1}^{\min(N,N-j+p+2)}\frac{(N-j)!}{(N-j-k+p+2)!}{(N-k+p-1)!}\frac{(j-1)(j-2)}{2}\\ =&\sum_{p=1}^{x}\sum_{j=3}^{N}\sum_{k=x+2}^{\min(N,N-j+p+2)}\sum_{q=x+1}^{\min(N-j+p+1,k-1)}\frac{(N-j)!}{(N-j-k+p+2)!}{(N-k+p-1)!}\frac{(j-1)(j-2)}{2}\\ =&\sum_{p=1}^{x}\sum_{j=3}^{N}\sum_{k=x+2}^{\min(N,N-j+p+2)}(k-x-1)\frac{(N-j)!}{(N-j-k+p+2)!}{(N-k+p-1)!}\frac{(j-1)(j-2)}{2}\\ =&\sum_{j=3}^{N}(N-j)!\frac{(j-1)(j-2)}{2}(j-3)!\sum_{k=x+2}^{\min(N,N-j+x+2)}(k-x-1)\sum_{p=1}^{x}\frac{(N-k+p-1)!}{(N-j-k+p+2)!(j-3)!}\\ =&\sum_{j=3}^{N}(N-j)!\frac{(j-1)(j-2)}{2}(j-3)!\sum_{k=x+2}^{\min(N,N-j+x+2)}(k-x-1)\sum_{p=\max(1,k-(N-j+2))}^{x}\binom{N-k+p-1}{j-3} \end{aligned}

然后最后那个东西直接 O(1) 上指标求和即可。但是 i=1 还有个余项，化简之后是：

\sum_{j=2}^{\min(N,p+1)} (j-1)\frac{(N-j)!}{(p+1-j)!}

这个化简是平凡的。

感觉最妙的是凑了个组合数出来。人类智慧发力了？

到这里已经可以通过本题了，但是如果你有耐心稍加拆解，一个线性做法也是显然的。但是这里不赘述了，因为没有什么本质观察。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5, mod = 1e9 + 7;
int n, x, fac [N + 5], inv [N + 5], ifac [N + 5], ans;
int C (int n, int m) { 
    if (n < m) return 0;
    return fac [n] * ifac [m] % mod * ifac [n - m] % mod; 
}
int Cupper_bound (int l, int r, int k) { 
    if (l > r) return 0;
    return (C (r + 1, k + 1) + mod - C (l, k + 1)) % mod;
}
void Turn () {
    cin >> n >> x; x = n - x;
    for (int j = 3 ; j <= n ; j ++) {
        int val = fac [n - j] * (j - 1) % mod;
        (val *= (j - 2) * inv [2] % mod * fac [j - 3] % mod) %= mod;
        for (int k = x + 2 ; k <= min (n, n - j + x + 2) ; k ++) {
            int lo = max (1ll, k - (n - j + 2));
            (ans += val * (k - x - 1) % mod * 
                Cupper_bound (n - k + lo - 1, n - k + x - 1, j - 3)) %= mod;
        }
    }
    for (int p = 1 ; p <= x ; p ++)
        for (int j = 2 ; j <= min (p + 1, n) ; j ++)
            (ans += (n - x) * fac [p - 1] % mod * (j - 1) % mod *
                fac [n - j] % mod * ifac [p + 1 - j] % mod) %= mod; 
    cout << ans << endl;
}

int _; void Init () {
//  ios :: sync_with_stdio (0); cin. tie (0); cout. tie (0);
    _ = 1;
//  freopen (".in", "r", stdin);
//  freopen (".out", "w", stdout);
//  cin >> _;
    fac [0] = ifac [0] = inv [1] = 1;
    for (int i = 2 ; i <= N ; i ++)
        inv [i] = (mod - mod / i) * inv [mod % i] % mod;
    for (int i = 1 ; i <= N ; i ++)
        fac [i] = fac [i - 1] * i % mod,
        ifac [i] = ifac [i - 1] * inv [i] % mod;
}

    signed main () { Init ();
    while (_ --> 0)
    Turn (); return 0; }