题面

思路

一眼看过去以为NOI2018的题出出来了= =贼吓人

首先，对于这个难度，我们有一个比较明显的结论：

一个序列的难度，等于这个东西：

$hard=max(\sum_{j=i+1}^n[a_j<a_i])(i=1...n)$

也就是一个元素后面的元素比它小的个数的最大值

证明显然，每轮操作只会把它后面的一个东西放到前面来，证毕

统计难度

我们令$f[i][j]$表示长度为$i$的序列难度为$j$的方案数

这个东西好像不太好算，没法确定难度正好为$j$，那我们做一个前缀和，令$F[i][j]$表示难度小于等于$j$的方案数

这个东西可以用组合意义算出来：

$F[i][j]=(j+1)^(i-j)\ast j!(i\geq j)$

$F[i][j]=i!(i < j)$

下面那个比较显然，上面那个的意义是，从最前面开始放，每次都有令上面那个统计序列难度的那个式子的答案在$[0,j]$区间内任选的$j+1$个选择，选到$n-m$个之后后面的就随便放了

然后，我们用$F$表示$f$：$f[i][j]=F[i][j]-F[i][j-1]$

字典序

对于字典序这里，我们依旧是从前往后逐位确定，每次还是枚举后面有多少个比它小的

不难发现，在确定了一个位置的后面有$m$个比它小的以后，后面的就随便放了，每次的方案数是$F[i][m]$

而当还没有这样的位置时，每次处理区间$[t,n]$等价于把$[1,n-t+1]$中的数放进去并满足条件，方案数为$f[t][m]$

这样确定之后，最后再扫一遍确定每个位置的元素是什么就好了

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

inline ll read(){

    ll re=0,flag=1;char ch=getchar();

    while(ch>'9'||ch<'0'){

        if(ch=='-') flag=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

    return re*flag;

}

ll n,m,k;

ll f[50],g[50],fac[50];

ll qpow(ll a,ll b){

    ll re=1;

    while(b){

        if(b&1) re=re*a;

        a=a*a;b>>=1;

    }

    return re;

}

ll rk[50],vis[50];

int main(){

    n=read();m=read();k=read();

    ll i,j;

    fac[0]=1;

    for(i=1;i<=n;i++) fac[i]=fac[i-1]*(ll)i;

    for(i=0;i<=n;i++) f[i]=((i<m)?fac[i]:(fac[m]*qpow(m+1,i-m)));

    for(i=0;i<=n;i++) g[i]=f[i]-((i<(m-1))?fac[i]:(fac[m-1]*qpow(m,i-m+1)));

    ll cur,flag=0;

    for(i=1;i<=n;i++){

        for(j=1;j<=n-i+1;j++){

            if(flag||j==m+1) cur=f[n-i];

            else cur=g[n-i];

            if(cur>=k){

                rk[i]=j;

                if(j==m+1) flag=1;

                break;

            }

            else k-=cur;

        }

    }

    for(i=1;i<=n;i++){

        cur=0;

        for(j=1;j<=n;j++){

            cur+=(!vis[j]);

            if(cur==rk[i]){

                printf("%lld ",j);

                vis[j]=1;break;

            }

        }

    }

}

巴特西

冒泡排序 [组合数学+dp]

题面

思路

统计难度

字典序

Code

最新文章

热门文章