【题解】LOJ 2719 「NOI2018」冒泡排序

Problem

对于一个 $1-n$ 的排列,设对其进行冒泡排序需要交换的次数 $=\frac{1}{2}\sum_{i=1}^{n}|i-p_i|$ ,则称其为好的排列

求字典序大于 $q$ 的好的排列的数量

Thought

若有一个不应该往前移动的数字往前移动了,那么这肯定不是一个好的排列
需要保证任意一个数字在前面比它大的数字的个数要小于等于它需要前移的次数

对于任意 $p_i$ ,前面比它大的数的数量 $s_i$ 满足 $s_i\leq min(i-p_i,0)$ ,则该排列为一个好的排列

这个结论太弱了,做不了啊...

一个比较强的结论是若出现 长度 $\ge3$ 的下降子序列 ,那么不合法
因为这样的话中间的值需要先前移再后移,显然是有多余操作的
否则可以证明不会有多余操作

任意一对数中较大的数的调整后,较小的数后面不可能出现一个更小的数,所以它不会再向后调整导致(向前,向后)操作的产生

先不考虑字典序怎么做

假设现在已经填了前 $k$ 个,对后面选择的影响仅仅是后面剩下的数前 $k$ 数中最大值大的有多少个

因为假设出现了任意一个下降子序列 $(i,j)$ ,那么 $j$ 一定只能是 $<i$ 的所有数中最小的一个,也不会对后面的选择产生任何的限制,所以说并没有什么卵用

并且显然的,数的具体大小也没有什么意义,只需要知道其相对关系就好了

用 $f[i][j]$ 表示现在填了前 $i$ 个,其中未填的数中比前 $i$ 个数中最大的数大的有 $j$ 个
发现这些比最大值还要大的和答案一点关系都没有,那么可以随便选一个进行转移:

$$ f[i][j]\to f[i+1][j'] $$

其中 $j'\leq j-1$

可以选择剩下的数中任意一个比最大值小的,当然,需要存在有比最大值小的

$$ f[i][j]\to f[i+1][j] $$

其中 $i+1+j\leq n$

就相当于是从 $(0,n)$ 出发到 $(n,0)$ 不能越过 $y=n-x$ 的路径数呗,答案为:

$$ C_{2n}^{n}-C_{2n}^{n-1} $$

如何处理上界问题呢?

发现加入限制之后就相当与是给定的路径的下面节点到终点的路径条数和

对于下面的样例,我们可以画出对应的图形:

4
1 4 2 3

规定的线路即 $A-C-D-B$

在线路之下的点即为 $I,J,G$ ,相应的,最终答案应该转化为 $G\to B+H\to B+I\to B$ 的不经过 $y=n-x$ 的路径条数

利用一点小技巧,可以将在 $x$ 坐标相等的连续点的路径转化为一个点,同时按照一般的方法,做出 $B$ 的对称点 $B'$ ,即可在 $O(1)$ 的时间内计算某个特定横坐标的答案

即点 $E-B$ 的方案减去 $E-B'$ 的方案
问题完美解决

注意:下界对应的线段不合法时就要直接退出了

预先处理组合数之后,时间复杂度 $O(n)$ ,可以通过 $100pt$ 的数据

Code

#include <bits/stdc++.h>
using namespace std;

int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 1200010;
const int MOD = 998244353;

int n;
int p[N];

int inv[N], invPro[N], pro[N];

void prepare() {
    inv[0] = invPro[0] = pro[0] = 1;
    inv[1] = invPro[1] = pro[1] = 1;
    for(int i = 2; i <= 1200000; ++ i) {
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
        invPro[i] = 1ll * invPro[i - 1] * inv[i] % MOD;
        pro[i] = 1ll * pro[i - 1] * i % MOD;
    }
}

int C(int n, int m) {
    return ((m > n) || (m < 0) || (n < 0)) ? 0 : 1ll * pro[n] * invPro[m] % MOD * invPro[n - m] % MOD;
}

int pre[N], nxt[N];

int erase(int x, int MIN) {
    if(pre[x])
        nxt[pre[x]] = nxt[x];
    if(nxt[x] <= n)
        pre[nxt[x]] = pre[x];
    if(x == MIN)
        return nxt[x];
    return MIN;
}

void work() {
    n = read();
    for(int i = 1; i <= n; ++ i) {
        p[i] = read();
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    int MIN = 1;
    int ans = 0, flag = 1;
    int two = 0, now = 0;
    for(int i = 1; i < n && flag; ++ i) {
        if(p[i] > now)
            now = p[i];
        else if(p[i] != MIN)
            flag = 0;
        MIN = erase(p[i], MIN);

        int X = n - i,  Y = n - now;
        ans += C(X + Y, X + 1);
        if(ans >= MOD) ans -= MOD;
        ans -= C(X + Y, X + 2);
        if(ans < 0) ans += MOD;
    }

    printf("%d\n", ans);
}

int main() {
    freopen("inverse.in", "r", stdin);
    freopen("inverse.out", "w", stdout);
    prepare();
    int t = read();
    while(t --)
        work();
    return 0;
}
Comments

添加新评论