自动搬运

查看原文

来自洛谷，原作者为

	dtcxzyw **

搬运于2025-08-24 22:02:33，当前版本为作者最后更新于2018-07-28 20:34:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是FJWC2018的模拟考题。

我当时细节没有调对，然后就愉快地从100变为0分。。。

以下为题解：

考虑两个相似序列的共性：

1. 它们在原序列的位置相同；
2. 它们“离散化”后的序列相同（$C(P,x)$实质上是离散化后的下标）。

因为序列离散化后是一个排列，易知一个长度为i的排列可由$C[n][i]*(n-i)!$个长度为n的排列的子串离散化得到。

(即选择了$i$个数固定在子串中，剩余$n-i$个数自由排列)

所以我们可以先预处理$cnt[i][j]$表示长度为$i$，逆序对数不超过$j$的排列数，统计答案时，枚举排列子串的长度i，答案为

$ans=\sum_{i=1}^n{cnt[i][m](n-i+1)(C[n][i]*(n-i)!)^2}$

接下来讲讲如何预处理$cnt[i][m]$:

首先，数据范围中给出的$m<=1e6$过大，因为一个长为$n$的排列最多产生$\frac{n(n-1)}{2}$对逆序对，$query$时限制一下就好。

考虑往一个长度为$i-1$的排列里插入i，我们很容易得到一个$O(n^4)$的dp，显然会TLE。

打表可发现$cnt$的求法和组合数类似(超出定义域时值为0)：

$cnt[i][j]=cnt[i][j-1]+cnt[i-1][j]-cnt[i-1][j-i]$

于是预处理复杂度降为$O(n^3)$

dp出长度为i，逆序对数为j的排列数后，做个前缀和就好了。

时间复杂度$O(n^3+Tn)$

以下是代码：

#include <algorithm>
#include <cstdio>
#include <vector>
int read() {
    int res = 0, c;
    do
        c = getchar();
    while (c < '0' || c > '9');
    while ('0' <= c && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    return res;
}
const int size = 505, mod = 1000000007;
int add(int a, int b) {
    a += b;
    return a < mod ? a : a - mod;
}
int sub(int a, int b) {
    a -= b;
    return a >= 0 ? a : a + mod;
}
std::vector<int> cnt[size];
int C[size][size], fac[size];
typedef long long Int64;
#define asInt64(x) static_cast<Int64>(x)
void pre(int n, int m) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = asInt64(fac[i - 1]) * i % mod;
    C[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
    }
    cnt[0].push_back(1);
    for (int i = 1; i <= n; ++i) {
        int lsiz = cnt[i - 1].size();
        int cur = std::min(m, i * (i - 1) / 2);
        cnt[i].resize(cur + 1);
        cnt[i][0] = 1;
        for (int j = 1; j <= cur; ++j) {
            cnt[i][j] = cnt[i][j - 1];
            if (j < lsiz) cnt[i][j] = add(cnt[i][j], cnt[i - 1][j]);
            int off = j - i;
            if (0 <= off && off < lsiz)
                cnt[i][j] = sub(cnt[i][j], cnt[i - 1][off]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        int siz = cnt[i].size();
        for (int j = 1; j < siz; ++j)
            cnt[i][j] = add(cnt[i][j - 1], cnt[i][j]);
    }
}
int query(int n, int m) {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        Int64 val = asInt64(C[n][i]) * fac[n - i] % mod;
        int cur = cnt[i].size() - 1;
        res = (res + val * val % mod * cnt[i][std::min(cur, m)] % mod * (n - i + 1)) % mod;
    }
    return res;
}
struct Query {
    int n, m;
} Q[10005];
int main() {
    int t = read();
    int maxn = 0, maxm = 0;
    for (int i = 0; i < t; ++i) {
        Q[i].n = read();
        maxn = std::max(maxn, Q[i].n);
        Q[i].m = read();
        maxm = std::max(maxm, Q[i].m);
    }
    pre(maxn, maxm);
    for (int i = 0; i < t; ++i)
        printf("%d\n", query(Q[i].n, Q[i].m));
    return 0;
}