【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}= | ∑n≤sum nleq | 特殊性质 | 测试点 | nmax=n_{max}= | ∑n≤sum 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);}" qry(int a){ll r="0;while(a)r+=bt[a],a-=(a&-a);return" r;} ksm(ll a,ll b){ res="1;" while(b){ if (b&1) 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]<tem;" tem="min(tem,b[i]);" if (tem<="0)" break; ans="(ans+solve(n-i+1,tem-1))%mod;" (!flag&&c[i]!="a[i]-1)" } cout<