1. 题目

传送门=￣ω￣=

2. 题解

看上去非常难的样子，其实还好。

考虑枚举相似区间长度 $i$，计算每个 $i$对答案的贡献。

设 $f[i][j]$表示 $1,2,3,…,i$的排列中逆序对个数小于等于 $j$的有多少个。

$ans = \sum _ {i = 1} ^ {n} f[i][E] \times (n – i + 1) \times [C _ n ^ i \times (n – i)!] ^ 2$

其中 $C _ n ^ i \times (n – i)!$表示从 $n$个元素里选出 $i$个组成 “相似区间”，剩下的 $n – i$个元素随便排列，平方是因为有两个数组。

$n – i + 1$表示可以把相似区间插入到 $n – i$个元素形成的 $n – i + 1$个间隔中。

问题是怎么计算 $f[i][E]$

设 $h[i][j]$表示 $1, 2, 3, … ,i$的排列中逆序对个数等于 $j$的有多少个。

可以枚举前 $i – 1$位数字中比第 $i$位数字大的有多少个。

得到：

$h[i][j] = \sum _ {k = 0} ^ {i – 1} h[i – 1][j – k]$

计算的时候用一个前缀和就行了。

最后把 $h$做一个前缀和就得到 $f$了。

预处理 $f$复杂度 $O(n ^ 3)$，单次询问复杂度 $O(n)$

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

代码：

#include <bits/stdc++.h>

#define NS (505)
#define ES (124755)
#define MOD (1000000007)

using namespace std;

inline int pls(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int mns(int a, int b) {return a - b < 0 ? a - b + MOD : a - b;}

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int ToT, n, E, f[NS][ES], g[NS], sum[ES], C[NS][NS], P[NS];

void Init()
{
    f[1][0] = 1;
    for (int i = 2; i <= 500; i += 1)
    {
        g[i] = (i * (i - 1)) >> 1;
        sum[0] = f[i - 1][0];
        for (int j = 1; j <= g[i]; j += 1)
            sum[j] = pls(sum[j - 1], f[i - 1][j]);
        for (int j = 0; j <= g[i]; j += 1)
            if (j < i) f[i][j] = sum[j];
            else f[i][j] = mns(sum[j], sum[j - i]);
    }
    for (int i = 1; i <= 500; i += 1)
        for (int j = 1; j <= g[i]; j += 1)
            f[i][j] = pls(f[i][j], f[i][j - 1]);
    for (int i = 0; i <= 500; i += 1) C[i][0] = C[i][i] = 1;
    for (int i = 2; i <= 500; i += 1)
        for (int j = 1; j < i; j += 1)
            C[i][j] = pls(C[i - 1][j], C[i - 1][j - 1]);
    P[0] = 1;
    for (int i = 1; i <= 500; i += 1)
        P[i] = 1ll * P[i - 1] * i % MOD;
}

int main(int argc, char const* argv[])
{
    IN(ToT), Init();
    while (ToT--)
    {
        IN(n), IN(E); int ans = 0;
        for (int l = 1; l <= n; l += 1)
        {
            ans = pls(ans,
                1ll * (n - l + 1)
                * C[n][l] % MOD * P[n - l] % MOD
                * C[n][l] % MOD * P[n - l] % MOD
                * f[l][min(E, g[l])] % MOD);
        }
        printf("%d\n", ans);
    }
    return 0;
}