【NOI 2018】冒泡排序 / 题解

【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

输出

9

数据范围和提示

测试点

nmax=n_{max}=

nsum nleq

特殊性质 测试点

nmax=n_{max}=

nsum nleq

特殊性质
1

88

5nmax5n_{max}

13

144144

700700

2

99

5nmax5n_{max}

14

166166

700700

3

1010

5nmax5n_{max}

15

200200

700700

4

1212

5nmax5n_{max}

16

233233

700700

5

1313

5nmax5n_{max}

17

777777

40004000

i  pi=iforall i ~~p_i=i

6

1414

5nmax5n_{max}

18

888888

40004000

7

1616

5nmax5n_{max}

19

933933

40004000

8

1616

5nmax5n_{max}

20

10001000

40004000

9

1717

5nmax5n_{max}

21

266666266666

20000002000000

i  pi=iforall i ~~p_i=i

10

1818

5nmax5n_{max}

22

333333333333

20000002000000

11

1818

5nmax5n_{max}

23

444444444444

20000002000000

12

122122

700700

i  pi=iforall i ~~p_i=i

24

555555555555

20000002000000

. . . . 25

600000600000

20000002000000

思路

题目的限制可以转化为不存在长度>=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]
Show Comments