多校联测11 8ady

题目大意

有一个排列$a_1,a_2,\dots ,a_n$，我们现在进行如下操作：

for(int i=1;i<=n-m+1;i++) sort(a+i,a+i+m);

设最后的结果为$b_1,b_2,\cdots ,b_n$，求满足条件的$a$中字典序第$k$小的$a$。

$1\le n\le 10^6,m\le n,1\le k\le 10^{18}$，$b_i$是$1$到$n$的一个排列。

题解

由题意可得$b_i$是$a_1,a_2,\dots ,a_{\min (i+m-1,n)}$中，满足不在$b_1,b_2,\dots ,b_{i-1}$中的最小的数。

那么，当$b_{i-1}>b_i$，就一定有$a_{i+m-1}=b_i$。

把这些已经确定的$b_i$去掉，剩下的问题等价于$n$变小，$m,k$不变，$b_i=i$的子问题。

下面，我们假设$b_i=i$。

考虑从小到大将每一个$i$填入$a$中，易得$i$需要填在$[1,\min (i+m-1,n)]$中任意没填过的位置，那么填$i$的方案数为$\min (m,n-i+1)$。

然而，因为方案数很大，而$k$相对没那么大，所以$a$有一个前缀都满足$a_i=i$。

设$f_i$表示满足上面条件的前缀为$n-i$，也就是后面有最多$i$个数不满足，那么

$f_i=f_{i-1}\times \min (m,i)$

当$m=1$时，显然只有一个答案。因为保证有解，这种情况下$k=1$。

当$m>1$时，$f_i\ge 2^{i-1}$，可得$f_{62}\ge k$

那么，我们只需取最后$\min (n,62)$个位置，后面用一个状压维护状态，再枚举每一位填什么即可。细节见代码。

时间复杂度为$O(n+v^3)$，其中$v=\min (n,62)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[1000005],c[1000005],num[1000005],z[1000005];
long long k;
long long gt(int t,int w,long long now){long long re=1;for(int i=1;i<=t;i++){if((now>>i-1)&1){if(re>k/(min(i+m-1,t)-w)+1) return k+1;re=re*(min(i+m-1,t)-w);if(re>k) return k+1;++w;}}return re;
}
void dd(int l,int t){long long now=(1ll<<t)-1;for(int i=1;i<=l-t;i++) c[i]=num[i];for(int i=t;i>=1;i--){for(int j=1;j<=t;j++){if((now>>j-1)&1){long long vt=gt(t,t-i+1,now^(1ll<<j-1));if(k>=vt) k-=vt;else{c[l-i+1]=num[l-t+j];now^=(1ll<<j-1);break;}}}}
}
int main()
{scanf("%d%d%lld",&n,&m,&k);--k;for(int i=1;i<=n;i++){scanf("%d",&b[i]);}int lst=b[1],cnt=0;for(int i=2;i<=n;i++){if(lst>b[i]){a[i+m-1]=b[i];z[b[i]]=1;}else lst=b[i];}for(int i=1;i<=n;i++){if(!z[i]) num[++cnt]=i;}dd(cnt,min(cnt,62));int now=1;for(int i=1;i<=n;i++){if(!a[i]){a[i]=c[now];++now;}printf("%d ",a[i]);}return 0;
}