题意大概是给定一个长度为$n$的排列$p$，求有多少长度为$n$的排列满足冒泡排序的交换次数为$\frac{1}{2} \sum\limits_{i = 1}^{n}|i - p_{i}|$。
可以发现，该式子是冒泡排序复杂度的下界，任意一个数想要回到规定的位置至少要被交换$|i - p_{i}|$次，即在排序过程中不浪费任何一次交换，每一个数都只能向它归回原位的方向走。
稍加思索，可以得出一个结论：
- 任何一个最长下降子序列长度超过$2$的排列一定是不合法的。
- 任何一个最长下降子序列不超过$2$的排列一定合法。
考虑第一句话的正确性：
试想处于中间的那个数，左边存在比它大的数，右边存在比它小的数，那么该数一定会被向左交换一次，也一定会被向右交换一次，然后这两次交换是对该数无意义的，因为它向两个方向走了，导致位置没有改变。所以这两次的交换被浪费，故一定不合法。
考虑第二句话的正确性：
试想一个逆序对，处于右边小的数一定会向左走，如果要使它不合法，必定要令它向右至少走一步，那就意味着右边存在更小的数，与原条件矛盾，对于左边的数同理。
有了这个结论，不考虑起始字典序的限制，我们就可以写出一个$O(n^{2})$的dp，考虑$f_{i,j}$表示前$i$数，记$i$个数中最大的数为$mx$，剩余数中有$j$个数比$mx$小，此时的方案数。
此处有两种转移：
- 选一个比$mx$大的数，不会破坏上述结论。
- 选剩余几个比$mx$小的数中最小的那个。如果出现了长度为$3$的最长下降子序列，那在它第二个数的时候就不会被选了，因为它不是最小的数。在$j = 0$时不能用此转移。
这样就能$O(n^{2})$做一个dp了。我们把dp的两维看作二维坐标，看看它的实际意义。
我们每次横坐标$i$加$1$时，纵坐标$j$每次加一个非负整数，或者减一。其中$j$总是非负的，那由$(0,0)$走到$(n,0)$的一条合法路径就是一个合法答案。
由于每次增加的是任意非负整数，不好计算，我们甚至可以把它转化成括号序列。每次横坐标增加$1$个单位时，相当于加了一个右括号，在这之前可以加任意多个左括号，对应了纵坐标增加量加一，即将$j-1$对应了不加左括号。显然这个模型和上一个完全一样，而且你可以快速的用组合数算出括号序列的总数。
最后我们来考虑初始字典序的限制，通过上述论证，我们知道一个字典序对应了一个括号序列，我们考虑在哪一个位置突破了字典序的限制，那么显然以后就可以随机游走了。突破字典序的限制，意味着选一个比当前更大的数（一定会更大，如果选择了一个比$mx$小但比当前数大的一个数就会违反只能选最小的数的规则），我们只要比原先多加一个左括号就可以了（不需要多加，因为那会被随机游走枚举到）。
此处有一个小trick：我们在计算栈中还有$x$个左括号，还有$y$个右括号将来匹配的括号序列方案数时，组合数算出来的是随机游走的方案数，事实上我们必须保证纵坐标非负，我们只需要容斥掉不合法的就可以了。具体来讲就是将我们要算的起点按直线$y=-1$镜像，再计算没有右括号数限制的随机游走的方案数，因为每一个算出来的方案一定会经过$y=-1$这条直线，我们把这个方案表示的路径在第一次触碰直线$y=-1$之前的那段向上翻回去，就能对应了原起点在游走时被计算进去的一条不合法路径，把这个减掉就可以了。
所以总的时间复杂度是$O(n)$的。
$\bigodot$技巧＆套路：
- 冒泡排序的复杂度（交换次数）分析。
- 随机游走和括号序列计数的联系。
- 有限制的括号序列计数的容斥转化技巧。
#include <cstdio>
#include <cstring>
#include <algorithm> typedef long long LL;
const int N = , MOD = ; int tc, n;
int fac[N], ifac[N], p[N >> ], vis[N >> ]; inline void Read(int &x) {
x = ; static char c;
for (c = getchar(); c < '' || c > ''; c = getchar());
for (; c >= '' && c <= ''; x = (x << ) + (x << ) + c - '', c = getchar());
} inline int Pow(int x, int b) {
static int re;
for (re = ; b; b >>= , x = (LL) x * x % MOD)
if (b & ) re = (LL) re * x % MOD;
return re;
} inline int C(int x, int y) {
if (x < y) return ;
return (LL) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
inline int Cal(int x, int y) {
if (x < y) return ;
int dis = * x - y, re1 = C(dis, x);
if (y + > dis) return re1;
return (re1 - C(dis, (dis + y) / + )) % MOD;
} int main() {
freopen("inverse.in", "r", stdin);
freopen("inverse.out", "w", stdout); fac[] = ;
for (int i = ; i < N; ++i) {
fac[i] = (LL) fac[i - ] * i % MOD;
}
ifac[N - ] = Pow(fac[N - ], MOD - );
for (int i = N - ; i >= ; --i) {
ifac[i - ] = (LL) ifac[i] * i % MOD;
} scanf("%d", &tc);
for (; tc; --tc) {
int re = , mx = , low = , he = ;
memset(vis, , sizeof vis);
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
Read(p[i]);
}
for (int i = ; i < n; ++i, --he) {
if (mx < p[i]) he += p[i] - mx;
mx = std::max(mx, p[i]);
for (vis[p[i]] = ; vis[low]; ++low);
re = (re + Cal(n - i + , he + )) % MOD;
if (mx > p[i] && p[i] > low) {
break;
}
}
printf("%d\n", (re + MOD) % MOD);
} return ;
}