P4769 [NOI2018]冒泡排序

    • 235通过
    • 764提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 卡特兰,Catalan 树状数组 NOI系列 2018 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    最近,小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 \times 10^5$。

    接下来一行会输入n 个正整数,对应于题目描述中的qi,保证输入的是一个1 到 n 的排列。

    输出格式:

    输出到文件inverse.out 中。

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

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

    输入输出样例

    输入样例#1: 复制
    1
    3
    1 3 2
    输出样例#1: 复制
    3
    输入样例#2: 复制
    1
    4
    1 4 2 3
    输出样例#2: 复制
    9

    说明

    下面是对本题每个测试点的输入规模的说明。

    对于所有数据,均满足T = 5 (样例可能不满足).
    记$n_{max}$ 表示每组数据中n 的最大值,
    $\sum n$ 表示所有数据的n 的和。

    测试点 $n_{max}=$ $\sum n\leq$ 特殊性质 测试点 $n_{max}=$ $\sum n\leq$ 特殊性质
    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$

    下面是对交换次数下界是$\frac{1}{2} \sum_{i=1}^n |i-p_i|$的证明。

    排序本质上就是数字的移动,因此排序的交换次数应当可以用数字移动的总距离 来描述。对于第i 个位置,假设在初始排列中,这个位置上的数字是$p_i$,那么我们需要将这个数字移动到第pi 个位置上,移动的距离是$|i-p_i|$。从而移动的总距离就是$\sum_{i=1}^n |i-p_i|$,而冒泡排序每次会交换两个相邻的数字,每次交换可以使移动的总距离至多减少2。因此$\frac{1}{2} \sum_{i=1}^n |i-p_i|$是冒泡排序的交换次数的下界。

    并不是所有的排列都达到了下界,比如在n = 3 的时候,考虑排列3 2 1, 这个排 列进行冒泡排序以后的交换次数是3,但是$\frac{1}{2} \sum_{i=1}^n |i-p_i|$ 只有2。

    【样例1 解释】 字典序比1 3 2 大的排列中,除了3 2 1 以外都是“好”的排列,故答案为3。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。