CF1777B题解

· · 题解

时间复杂度为 O(n+t) 的解法

这道题本来是很简单的，但是考场上看漏了“所有 n 之和不超过 10^5”这句话，于是想了半小时才想出如何把 O(tn) 优化到 O(t)，进而导致我最后只做出来 2 题……

闲话少说，让我们来看看这道题。非常容易想出一种暴力的做法，时间复杂度为 O(t \times n! \times n^2)，显然无法通过此题。

我们可以尝试找找规律：

当 n=1 时，共有 0 个。

当 n=2 时，共有 4 个。也可以枚举一下：

当 n=3 时，我们可枚举一共 3!=6 种可能：

等一下，我们发现长度固定的 a 的逆序对的个数是固定的！

那么我们只需要找其中一个 a 的逆序对个数，然后再乘上 n! 就可以了。再通过一些优化，时间复杂度降为 O(tn^2 \log n)。（因为计算阶乘需要 O(n) 的计算）。

但是显然，这个时间复杂度仍不让人满意。那有没有更快的方法呢？我们通过更多的枚举可以发现长度为 2n 的 a 的逆序对的数量为 n(n-1)，这个是考场找规律出来的。现在想到了证明：

因为 a 的逆序对的个数是固定的，所以我们考虑更简单的第一种，也就是 a = [1,2,\dots,n,n,n-1,\dots,2,1] 的时候。此时我们可以发现第一个数 1 没有与它构成的逆序对，而第二个数有 1 个，第三个数有 2 个……到了第 n 个数 n 有 n-1 个。前 n 个数一共有 1+2+\dots+(n-1)+n 个逆序对，用等差数列求和公式可化简为 \frac{n(n-1)}{2}。后面的 n 个数也是一样，所以一个 a 的逆序对个数就是 \frac{n(n-1)}{2} \times 2 = n(n-1)。那么答案即为 n! \times n(n-1)。时间复杂度降为 O(tn)，可以通过此题。

但是，但是，我不是说有 O(n+t) 的解法吗？其实也很简单，我们可以 O(n) 预处理 1 到 n 的阶乘（设 i 的阶乘为 f_i），然后再在线计算 f_n \times n(n-1) 即可。时间复杂度为 O(n+t)，空间复杂度为 O(n)，自认为这种解法比较优秀。

考场代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 1e5+1;

long long t, n, x = 1;
long long f[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for (int i=1; i<MAXN; i++){
        x = (x*i)%MOD;
        f[i] = x;
    }

    cin >> t;
    while (t--){
        cin >> n;
        cout << (f[n]*(n-1)%MOD)*n%MOD << '\n';
    }

    return 0;
}

我自己也搞了一道题，和这道题数据范围的区别。各位可以尝试用上面的方法做一下。