【NOI 2018】冒泡排序 / 题解

题目描述

最近，小S 对冒泡排序产生了浓厚的兴趣。为了问题简单，小 S 只研究对 1 到n 的排列的冒泡排序。

下面是对冒泡排序的算法描述。

输入：一个长度为n 的排列p[1…n]

输出：p 排序后的结果。

for i = 1 to n do
    for j = 1 to n - 1 do
        if(p[j] > p[j + 1])
            交换p[j] 与p[j + 1] 的值

冒泡排序的交换次数被定义为交换过程的执行次数。可以证明交换次数的一个下界是 $frac{1}{2} sum_{i=1}^n |i-p_i|$。$p_i$是排列p 中第i 个位置的数字。如果你对证明感兴趣，可以看提示。

小S 开始专注于研究长度为n 的排列中，满足交换次数$= frac{1}{2} sum_{i=1}^n |i-p_i|$ 的排列（在后文中，为了方便，我们把所有这样的排列叫“好”的排列）。他进一步想，这样的排列到底多不多？它们分布的密不密集？小S 想要对于一个给定的长度为n 的排列q，计算字典序严格大于q 的“好”的排列个数。但是他不会做，于是求助于你，希望你帮他解决这个问题，考虑到答案可能会很大，因此只需输出答案对998244353 取模的结果。

输入和输出

输入格式

从文件inverse.in 中读入数据。

输入第一行包含一个正整数T，表示数据组数。

对于每组数据，第一行有一个正整数n, 保证 $n leq 6 imes 10^5$
接下来一行会输入n 个正整数，对应于题目描述中的$q_i$，保证输入的是一个1 到 n 的排列。

输出格式

输出到文件inverse.out 中。

输出共T 行，每行一个整数。

对于每组数据，输出一个整数，表示字典序严格大于q 的“好”的排列个数对 998244353 取模的结果。

样例

输入

1
4
1 4 2 3

输出

数据范围和提示

测试点	$n_{max}=$	$sum nleq$	特殊性质	测试点	$n_{max}=$	$sum nleq$	特殊性质
1	$8$	$5n_{max}$	无	13	$144$	$700$	无
2	$9$	$5n_{max}$	无	14	$166$	$700$	无
3	$10$	$5n_{max}$	无	15	$200$	$700$	无
4	$12$	$5n_{max}$	无	16	$233$	$700$	无
5	$13$	$5n_{max}$	无	17	$777$	$4000$	$forall i ~~p_i=i$
6	$14$	$5n_{max}$	无	18	$888$	$4000$	无
7	$16$	$5n_{max}$	无	19	$933$	$4000$	无
8	$16$	$5n_{max}$	无	20	$1000$	$4000$	无
9	$17$	$5n_{max}$	无	21	$266666$	$2000000$	$forall i ~~p_i=i$
10	$18$	$5n_{max}$	无	22	$333333$	$2000000$	无
11	$18$	$5n_{max}$	无	23	$444444$	$2000000$	无
12	$122$	$700$	$forall i ~~p_i=i$	24	$555555$	$2000000$	无
.	.	.	.	25	$600000$	$2000000$	无

思路

题目的限制可以转化为不存在长度>=3的下降子序列，这又可以转化为可以将序列划分为2个上升子序列。

首先我们用树状数组预处理出 $a_i$ ，后面的比它大的数的个数 $b_i$ ，以及前面的比它小的数 $c_i$。因为要保证字典序，我们就从前往后依次固定前 $i$ 个数，然后讨论后面的数字的顺序。

令前 $i$ 个位置中，最大的数是 $j$。我们发现，大于$j$的数的顺序不影响答案，然而小于 $j$ 的数必须从小到大按顺序填入（因为这些元素一定要被归入同一个上升子序列）。

所以，我们可以得到这个式子：$f(i,j) = sum_{k=0}^j f(i-1,j-k)$。

通过一些化式子的技巧，可以发现它恰好等于 $ binom{n+m-1}{m}- binom{n+m-1}{m-2}$。

然后就可以开始暴算啦！

代码

// inverse.cpp : Defines the entry point for the console application.
// XG Zepto, 7/26/2018. All rights reserved.

#include "stdafx.h"
#include 
#include 
#include 
#include 
#define ll long long
#define maxn 1200001
#define mod 998244353
using namespace std;
int bt[maxn<<1],n,a[maxn],b[maxn],c[maxn];
ll jc[maxn],ny[maxn];
void add(int a){while(a<=n)bt[a]++,a+=(a&-a);}
ll qry(int a){ll r=0;while(a)r+=bt[a],a-=(a&-a);return r;}
ll ksm(ll a,ll b){
    ll res=1;
    while(b){
        if (b&1) res=res*a%mod;
        a=a*a%mod;b>>=1;
    }
    return res;
}
void init(int ul){
    jc[0]=1;
    for (int i=1;i<=ul;i++)
        jc[i]=jc[i-1]*i%mod;
    ny[ul]=ksm(jc[ul],mod-2);
    for (int i=ul-1;i>=1;i--)
        ny[i]=ny[i+1]*(i+1)%mod;
    ny[0]=1;
}
ll com(int n,int m){
    return (jc[n]*ny[m]%mod*ny[n-m])%mod;
}
ll solve(ll n,ll m){
    if (!m) return 1;
    if (m==1) return n;
    return (com(n+m-1,m)-com(n+m-1,m-2)+mod)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    init(maxn-1);
    int T;cin>>T;while(T--){
        memset(bt,0,sizeof(bt));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=n;i>0;i--){
            b[i]=n-i-qry(a[i]);
            add(a[i]);
            c[i]=i-1-(n-a[i]-b[i]);
        }
        ll ans=0;int tem=n;
        for(int i=1;i<=n;i++){
            bool flag=b[i]