题解：P10592 BZOJ4361 isn

· · 题解

很好很好的算答案方式。

小 D 有一个长度为 n 的序列。如果序列不是非降的，他会选择一个元素删去，直到序列变成非降的，这时停止操作。求操作序列种类数，对 10^9+7 取模。

两个操作序列不同，当且仅当它们长度不同或者某一次操作删除的元素位置不同。

这个问题的难点在于，如果此时序列已经非降了那么此时必须停止。我们考虑如果没有这个限制的问题：

小 D 有一个长度为 n 的序列。如果序列不是非降的，他会选择一个元素删去，直到序列变成非降的，这时可以选择停止操作，也可以不停止。求操作序列种类数，对 10^9+7 取模。

我们考虑原序列的任意一个上升子序列对答案的影响，即有多少种将其它元素删除的方式，使得最终整个序列只剩这个子序列。

令这个上升子序列长度为 i。显然这个的答案是 (n - i)!，即其它元素可以任意选择顺序删除。

暴力枚举这个上升子序列仍然是指数复杂度。考虑 DP。

设 f(i, j) 表示有多少上升子序列以 i 结尾且长度为 j。转移显然：

f(i, j) = \left\{\begin{matrix}1 &, j=1 \\ \sum_{k=1}^{i-1}[a_k \le a_i]f(k,j-1) &,j \ne 1 \end{matrix}\right.

可以用树状数组轻易优化至 \mathcal O(n^2 \log n)。

考虑统计答案。令 g(i) = \sum_{j=1}^i f(j, i)，即有多少个上升子序列的长度为 i。那么答案为：

\sum_{i=1}^n g(i) \cdot (n - i)!

至此我们用 \mathcal O(n^2 \log n) 的复杂度通过了弱化版。

我们考虑原问题比弱化版的答案少在了哪些地方。即考虑一个上升子序列什么时候产生的贡献变小。

对于一个长度为 i 的上升子序列 s，如果存在 j 个长度为 i + 1 的上升子序列完全包含它，那么当小 D 通过若干次删除操作得到这 j 个子序列后，游戏应当在此时停止。不难发现只有这种情况会导致 s 不产生贡献。

所以答案比弱化版少了：

\begin{matrix} \sum_{s,j} j \times (n-(i+1))! \\ \tiny s\text{ is an increasing subsequence of length }i\text{ of }a.\\ \tiny {\text{There are }j\text{ increasing subsequences of length }i+1\text{ that completely contain }s.} \end{matrix}

暴力枚举 s 还是指数复杂度。

显然每个 s 对应的 j 的和为 g(i + 1) \cdot (i + 1)。这是因为一个长度 i + 1 的上升子序列中含有 i + 1 个这样的 s。

所以答案为：

\sum_{i=1}^n\left[ g(i) \cdot (n-i)! - g(i+1)\cdot (i+1)\cdot(n-i-1)! \right] 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2024, P = 1e9 + 7;

int n, a[N], b[N];
int f[N][N];        // 以 i 结尾的长度为 j 的子序列数量
int g[N], nums;

struct Tree {
    int tr[N];

    void modify(int x, int d) {
        for (int i = x; i <= nums; i += i & -i)
            tr[i] = (tr[i] + d) % P;
    }

    int query(int x) {
        int res = 0;
        for (int i = x; i; i -= i & -i)
            res = (res + tr[i]) % P;
        return res;
    }
}T[N];

int fac[N];

signed main() {
    fac[0] = 1;
    for (int i = 1; i < N; ++ i ) fac[i] = 1ll * fac[i - 1] * i % P;

    cin >> n;

    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        b[i] = a[i];
    }

    sort(b + 1, b + n + 1);
    nums = unique(b + 1, b + n + 1) - b - 1;

    for (int i = 1; i <= n; ++ i ) {
        a[i] = lower_bound(b + 1, b + nums + 1, a[i]) - b;
    }

    for (int i = 1; i <= n; ++ i ) {
        f[i][1] = 1;
        for (int j = 2; j <= i; ++ j ) {
            f[i][j] = T[j - 1].query(a[i]);
        }

        for (int j = 1; j <= i; ++ j ) {
            T[j].modify(a[i], f[i][j]);
        }
    }

    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= i; ++ j )
            g[j] = (g[j] + 1ll * fac[n - j] * f[i][j] % P) % P;

    int res = 0;
    for (int i = 1; i <= n; ++ i )
        res = ((res + g[i] - g[i + 1] * (i + 1) % P) % P + P) % P;
    cout << res;

    return 0;
}