多校联测11 8ady

题目大意

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

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

设最后的结果为$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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60