CTSC2016 香山的树 (KMP+dp)

我的做法比较奇怪

约定$\Sigma$为字符集

显然是要枚举答案，不断增大答案$S$的字典序，求出字典序$>S$的个数，考虑$dp$求解

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

因为要 $dp$ 的是一个循环同构串，不妨直接扩展为无限循环的串，$dp$一个 最小 的循环节

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

显然此时一个合法的长度为$i$的串只需要满足$i$中不会出现循环

设$f_i$为最小循环节为$i$的答案，一种Naive的思路是直接拿$|\Sigma|^i$计算，但是显然长度为$i$的会包含长度为$\forall d,d|i$的

即$g_i=|\Sigma|^i=\sum_{d|i}f(d)$，然后直接$O(n\ln n)$减去重复部分即可

由于题目要求是最小的循环，因此实际上每个循环有$i$中不同开始位置，所以答案应是$\frac{f_i} {i}$

接下来考虑字典序的问题：不妨枚举一个无限循环串$S$的最优匹配位置为$st$，然后$dp$一个长度为$i$的循环节

显然要满足的条件是：

1.$dp$了$i$个字符之后匹配状态为$st$

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

注意这里有一个问题，当匹配位置恰好等于$|S|$时，可能会将恰好为$S$的情况算入，因此要特判

3.中途不能匹配到比$st$更大的位置

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

1.串内出现了循环

可以考虑同样的容斥方法

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

这个我的处理方法非常暴力，考虑直接记录匹配过程中恰好为$st$的次数，这些位置都是可能的开始位置

不妨令$dp_{i,j,d}$表示当前$dp$了$i$位，匹配状态为$j$，中途出现了$d$个恰好为$st$的匹配位置

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

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

一个小优化：每次二分时，只有$st=|S|$或者$st=|S|-1$的部分需要重新$dp$

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

感觉这个$dp$明显太麻烦了，显然可以删掉一些东西

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);
}