「CTSC2016」香山的树 (KMP+dp)

Posted on Edited on In

「CTSC2016」香山的树 (KMP+dp)

题目大意

对于所有的串，满足：

  1. 其是本身的最小循环同构。
  2. 其最小循环同构位置唯一。

给定一个这样的串，求其字典序在所有合法串中的 \(\text{rank}\)，以及求 \(\text{rank}=k\) 的串。

简要分析

这是一个暴力的做法，有一定优化空间。

约定 \(\Sigma\) 为字符集。

显然是要枚举答案，求出当前字符串在所有答案中的 \(\text{rank}\) ，不断增大答案 \(S\) 的字典序。

求出字典序 \(>S\) 的个数，考虑 \(\text{dp}\) 求解。

比较大小可以想到要不断进行前缀匹配，因此考虑 \(\text{kmp}\)。

因为要 \(\text{dp}\) 的是一个循环同构串，不妨直接扩展为无限循环的串，\(\text{dp}\) 一个 最小 的循环节。

不妨先考虑没有字典序限制的简单情形，也就是抛开 \(\text{kmp}\) 判断字典序，计算长度为 \(i\) 的方案数。

对于限制条件 2 ，等价于不存在循环分解，可以对于长度进行有关倍数的容斥，即 \(g_i=f_i-\sum_{d|i,d<i} g_d\)。

对于限制条件 \(1\)，不妨枚举一个无限循环串 \(S\) 的最优匹配位置为 \(st\)，然后 \(\text{dp}\) 一个长度为 \(i\) 的循环节。

显然要满足的条件是：

  1. \(\text{dp}\) 了 \(i\) 个字符之后匹配状态为 \(st\)。

  2. 在 \(\text{dp}\) 过程中如果 \(\text{kmp}\) 出现失配，必须满足当前字符更大。

    注意这里的边界情况，当匹配位置恰好等于 \(|S|\) 时，可能会将恰好为 \(S\) 的情况算入，因此要特判。

  3. 中途不能匹配到比 \(st\) 更大的位置。

同样的会出现两种重复计算：

  1. 串内出现了循环，即上文提到的容斥。

  2. 多个不同的开始位置都合法。

由于不存在循环，即每一个循环同构的位置都不同，考虑直接记录匹配过程中恰好为 \(st\) 的次数，在最终方案里除掉。

由以上思路，定义 \(f_{i,j,d}\) 表示当前 \(\text{dp}\) 了 \(i\) 位，匹配状态为 \(j\)，中途出现了 \(d\) 个恰好为 \(st\) 的匹配位置。

在求解完所有 \(f_{i,j,d}\) 后，先对于长度倍数进行容斥，由于多了一个维度，容斥时实际上变成了 \(f_{i,j,d}-f_{i,jk,dk}\) 的形式。随后再除以 \(d\) 算进答案。

可以得到一个 \(O(n^3|\Sigma|)\) 的暴力 dp，算上枚举起始位置，复杂度为 \(O(n^4|\Sigma|)\)。

由于还需要按位二分答案，所以复杂度为 \(O(n^5|\Sigma|\log |\Sigma|)\)，实际可以通过。

一个小优化：每次二分时，只有 \(st=|S|\) 或者 \(st=|S|-1\) 的部分需要重新 \(dp\) （即 \(st<|S|-1\) 时 \(S\) 的变化与 \(\text{dp}\) 值无关）。

因此实际复杂度为 \(O(n^4|\Sigma|\log |\Sigma|)\)。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;

typedef __int128 ll;
//本地测试可以改成long long ，并且把下面的U=1e36改为U=1e18
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=52,S=26;
const ll U=1e36;

void chk(ll &a){ a>U && (a=U); }

int n,m;
ll k;
char s[N];
int nxt[N],trans[N][S];
void Init_KMP(){
	rep(i,2,m) {
		int j=nxt[i-1];
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) j++;
		nxt[i]=j;
	}
	rep(i,0,m) {
		rep(j,0,S-1) {
			int k=i,f=1;
			while(s[k+1]!=j+'a') {
				f&=j+'a'>s[k+1];
				if(!k) break;
				k=nxt[k];
			}
			if(s[k+1]==j+'a') k++;
			trans[i][j]=f?k:-1;
		}
	}
}

ll dp[N][N][N];
ll Ans[N];

ll Calc(int k=0){
	m=strlen(s+1),Init_KMP();
	ll ans=0;
	rep(st,(k?0:m-1),m) {
		Ans[st]=0;
		rep(i,0,n) rep(j,0,st) rep(d,0,n) dp[i][j][d]=0;
		dp[0][st][0]=1;
		rep(i,1,n) {
			rep(j,0,st) rep(d,0,i) if(dp[i-1][j][d]){ 
				rep(c,j==m?0:s[j+1]-'a',S-1) if(~trans[j][c]) {
					chk(dp[i][trans[j][c]][d+(trans[j][c]==st)]+=dp[i-1][j][d]);
				}
			}
		}
		rep(i,1,n) rep(d,0,n) if(dp[i][st][d]) {
			if(dp[i][st][d]==U) return U;
			rep(j,2,min(n/i,n/d)) dp[i*j][st][d*j]-=dp[i][st][d];
			if(i>m || st!=m) chk(Ans[st]+=dp[i][st][d]/d); // 特判了恰好为S的情况
		}
	}
	rep(i,0,m) chk(ans+=Ans[i]);
	return ans;
}

int main(){ 
	//freopen("treelabel.in","r",stdin),freopen("treelabel.out","w",stdout);
	scanf("%d%lld%s",&n,&k,s+1);
	k=Calc(1)-k+1;
	if(k<0) return puts("-1"),0;
	rep(i,1,n) {
		int l='a',r='a'+S-1,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			s[i]=mid,s[i+1]=0;
			if(Calc()>=k) res=mid,l=mid+1;
			else r=mid-1;
		}
		s[i]=res,s[i+1]=0;
		if(!res || Calc()==k) break;
	}
	puts(s+1);
}