千年大坑。

合法排列有什么性质

首先考虑排列如何达到交换下界。

单独的考虑排列中的一个数,对于其目标位置,容易发现每一次关于这个数的交换一定是朝着目标位置的方向换的。对于排列 $2,1$ ,$2$ 要到后面 $1$ 要到前面,所以交换不会浪费次数。但是如果在前面加上 $3$ ,$3$ 要到后面去,$2$ 位置不变,$1$ 要到前面去。

$3$ 往后面去的时候 $2$ 会往前走,$1$ 往前面去的时候 $2$ 又被搬回来,这样就浪费了交换次数。考虑一般情况,即排列中有 $a_i,a_j,a_k$ 满足 $i<j<k,a_i>a_j>a_k$ ,最终情况下 $a_i$ 一定是要到 $a_k$ 的后面的,$a_k$ 也一定是要到 $a_i$ 的前面,两者方向不同,中间的 $a_j$ 就会浪费交换次数。

所以如果当排列中出现了长度为 $3$ 甚至以上的子序列,并且满足子序列递减,那么排列不合法。

容易发现长度为 $2$ 甚至以下的递减子序列和其他递增子序列都不会浪费交换次数。

简单情况如何统计

首先考虑 $p_i=i$ ,也就是忽略字典序顺序。

设 $dp(i,j)$ 表示选了 $i$ 个数,最大值为 $j$ 的方案数。转移显然要么选一个更大的,要么选小于 $j$ 的数中最小的。

令小于 $j$ 的数中最小的数为 $a$ ,如果选了一个小于 $j$ 的数 $b$ 但 $a<b$ ,因为 $a$ 无论如何都要加入,也就只能以后加入,这样就形成了由 ${j,b,a}$ 组成的递减子序列。

转移式即:

$$
dp(i,j)=\sum_{k=i-1}^{j} dp(i-1,k)
$$

时间复杂度 $O(n^2)$ 。

如何快速求出 $dp$ 数组

观察 $dp$ 数组的转移式,会发现 $dp(i,j)=dp(i-1,j)+dp(i,j-1)$ 。

考虑将 $dp$ 搬到二维平面上,用点 $(i,j)$ 表示 $dp(i,j)$ 。每一次转移就是往前走一步或者往上走一步。但是不能出现 $j>i$ 的情况,转而言之就是不能越过 $y=x$ 这条直线,也就是不能触碰 $y=x-1$ 这条直线。

这是一个经典的套路:首先令按照上述方式走,没有直线限制走到点 $(i,j)$ 的方案数为 $f(i,j)$ 。

那么 $dp(i,j)$ 就是 $f(i,j)$ 减去非法情况。考虑将第一次触碰直线 $y=x-1$ 的点后面的路径按照直线 $y=x-1$ 翻转,也就是终点变成了 $(j+1,i-1)$ ,这样就可以得到:

$$
dp(i,j)=f(i,j)-f(j+1,i-1)
$$

现在考虑 $f(i,j)$ 如何求。

可以往左走也可以往上走,显而易见的有:

$$
f(i,j)={i+j \choose i}
$$

时间复杂度 $O(1)$ ,预处理要 $O(n)$ 。

对于另外一种处理 $dp$ 数组的想法

按照原来的 $dp$ 转移式子,同样放到二维平面来考虑。

直线的限制是一样的,同样的设没有直线限制走到点 $(i,j)$ 的方案数为 $g(i,j)$ 。现在需要考虑 $g(i,j)$ 如何求。

现在一共是走了 $i$ 步,然后每一步的步长总和为 $j$,步长可以为 $0$ 。可以转化为一共 $i$ 个盒子,$j$ 个小球,可以空盒子的方案数。于是就可以得到:

$$
g(i,j)={i+j-1 \choose i-1}
$$

需要注意的是,由于在这种情况下只能” 横着走”,即每一步 $i$ 必须加 $1$ 。从 $(0,0)$ 到 $(j+1,i-1)$ 的” 竖着走” 的方案数。对应过来就是到 $(i-1,j+1)$ 的” 横着走” 的方案数。

(不会玩,暂时留坑

字典序问题如何处理

(不知道为啥卡这卡好久 …(于是开始钻研题解 ×

比较容易的一个方法就是枚举位置 $i$,前 $i-1$ 个数都和 $p$ 的对应位置相同,第 $i$ 个数大于 $p_i$ ,然后将方案数加起来。

令 $mx=\max_{j=1}^{i-1}p_j$,$mi$ 为当前最小的可以填的数,讨论第 $i$ 位的方案。

重新定义 $dp$ :表示点 $(i,j)$ 到 $(n,n)$ 的方案数。

  • 如果 $p_i=mi$
    • 填 $mi$ 显然不合法。
    • 填一个满足 $mi<x<mx$ 的数 $x$,因为如果将 $mi$ 留到后面就会形成 ${mx,x,mi}$,不合法。
    • 填一个满足 $x>mx$ 的数 $x$,方案数为 $dp(i,mx+1)$ 。
  • 如果 $mi<p_i<mx$
    • 只能填满足 $x>mx$ 的数 $x$,方案数为 $dp(i,mx+1)$ 。
    • 当接下来处理 $i+1$ 时,由于第 $i$ 位填了 $p_i$ ,前面一定形成了 ${mx,p_i}$,而还有小于 $p_i$ 的元素没有填,接下来一定不存在合法方案了。
  • 如果 $p_i\geq mx$
    • 填一个满足 $x>p_i$ 的数 $x$,方案数为 $dp(i,p_i+1)$ 。

时间复杂度 $O(n)$ 。

Code

const int N=2e6+5;
int n=2e6,p[N],vis[N],fac[N],inv[N];

inline int C(int n,int m) {
    if(n<m||n<0||m<0) return 0;
    return mul(fac[n],mul(inv[m],inv[n-m]));
}
inline int dp(int i,int j) {
    if(i>j||j>n) return 0;
    return dec(C((n<<1)-i-j,n-i),C((n<<1)-i-j,n-i+1));
}

int main() {
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
    inv[n]=modpow(fac[n],mod-2);
    for(int i=n;i>=1;--i) inv[i-1]=mul(inv[i],i);

    int T=int(IN);while(T--) {
        IN(n);
        for(int i=1;i<=n;++i) IN(p[i]),vis[p[i]]=0;

        int mx=0,mi=1,ans=0;
        for(int i=1;i<=n;++i) {
            chkmax(mx,p[i]),pls(ans,dp(i-1,mx+1)),vis[p[i]]=true;
            while(vis[mi]) ++mi;
            if(mi<p[i]&&p[i]<mx) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code