P8859 冒泡排序 题解

· · 题解

type=1

一个显然的贪心策略是我们从小到大检查每个 i，若 i 已经在第 i 个位置那么跳过，否则移动 i 到正确位置，因为 [i,n] 中 i 一定是最小值所以一定可以操作，最优性也是显然的。

接下来考虑什么时候会省下一次操作，也就是 i 已经在第 i 位的情况。

移动 1\sim i-1 的时候 i\sim n 的相对顺序是不变的，因此如果初始排列中 i 的前面有大于 i 的数，就必须需要一次操作来复位，否则就可以省下一次操作。

于是 f(A)=n-\sum\limits_{i=1}^n[a_i=\max\limits_{j=1}^i a_j]，也就是总数减掉前缀最大值的个数。

dp，记 f_{i,j} 表示 i 个数前缀最大值数量是 j 的排列数量，从 i 转移到 i+1 的时候加入最小值，显然只有最小值放在开头才有贡献，于是 f_{i,j}=f_{i-1,j-1}+(i-1)f_{i-1,j}，最终答案是 f_{n,n-k}，时间复杂度 O(n^2)。

这个转移其实就是第一类斯特林数，一种比较直观的理解是把前缀最大值加上他后面的这一段区间看成一个圆排列，前缀最大值是这个圆排列的代表元，容易证明这是一个双射。

type=2

顺着上一问的思路继续，考虑 f(A)=k 的环排列的性质。

第一次操作无法经过整个环，且后续操作不会经过 1，因此一定存在一个位置不会被操作，我们在这里断环为链，于是环排列的 f(A) 就是对在每个位置断环为链之后求排列的答案取 \min，进一步转化为所有可能断出的排列中前缀最大值的 \max。

先考虑给定一个排列怎样求 f(A)，可以转化成图论问题求解。对于每个点在环上找到第一个在自己后面且大于自己的数字，向它连有向边，那么环排列的答案就是图中的最长路。

注意到有且仅有 n 所在的位置没有出边，且所有位置的连边都不会跨过 n，所以我们不妨钦定 n 在序列末尾，这样环就变成了链，且不会算重。

这样连边形成的结构是一个内向树，图中的最长路等价于将有向边视为无向边后，以 n 为根的树高。

容易证明对于所有满足父亲节点编号小于儿子节点编号的生成树和 n 在序列末尾的排列数量是双射，因此我们只要求出满足 i 的父亲小于 i，以 1 为根的生成树中树高是 n-k 的树的数量就是答案。

还是 dp，记 g_{i,j} 表示 i 个点组成的树高是 j 的树的数量，转移考虑合并 1 的子树和 2 的子树，枚举两边子树的深度可以得到转移方程 g_{i+j,\max(d_1,d_2+1)}=\dbinom {i+j-2}{i-1}g_{i,d_1}g_{j,d_2}。

直接转移是 O(n^4) 的，记 sum_{i,j} 表示 i 个点组成的树高小于等于 j 的树的数量，就可以直接前缀和转移，时间复杂度 O(n^3)。

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int n,m,t,f[501][501],g[501][501],sum[501][501],c[501][501];
inline int Mod(int x)
{
    return x>=mod? x-mod:x;
}
int main()
{
    cin>>n>>m>>t;
    if(t==1)
    {
        f[1][0]=1;
        for(int i=2;i<=n;++i)
        {
            f[i][0]=1;
            for(int j=1;j<i;++j)
                f[i][j]=Mod(f[i-1][j]+1ll*(i-1)*f[i-1][j-1]%mod);
        }
        cout<<f[n][m]<<'\n';
    }
    else
    {
        c[0][0]=1;
        for(int i=1;i<=n;++i)
        {
            c[i][0]=1;
            for(int j=1;j<=n;++j)
                c[i][j]=Mod(c[i-1][j]+c[i-1][j-1]);
        }
        g[1][1]=1;
        for(int i=1;i<=n;++i)
            sum[1][i]=1;
        for(int i=2;i<=n;++i)
            for(int j=2;j<=n;++j)
            {
                if(j<=i)
                    for(int k=1;k<i;++k)
                        g[i][j]=Mod(g[i][j]+1ll*c[i-2][k-1]*Mod(1ll*g[k][j]*sum[i-k][j-1]%mod+1ll*sum[k][j-1]*g[i-k][j-1]%mod)%mod);
                sum[i][j]=Mod(sum[i][j-1]+g[i][j]);
            }
        cout<<g[n][n-m]<<'\n';
    }
    return 0;
}