P4678 [FJWC2018]全排列题解

dtcxzyw · 2018-07-28 20:34:33 · 题解

这是FJWC2018的模拟考题。

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

以下为题解：

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

它们在原序列的位置相同；
它们“离散化”后的序列相同（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;
}

P4678 [FJWC2018]全排列 题解

P4678 [FJWC2018]全排列题解