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\)明显太麻烦了，显然可以删掉一些东西

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