记录编号	146723	评测结果	AAAAAAAAAA
题目名称	[SRM 467] 均匀字符串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2015-01-19 11:05:40	内存使用	58.69 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int HSIZE=50007;
typedef unsigned US;
typedef long long LL;
typedef long double LDB;
//我们用一个unsigned去表示一个状态,每四个bit一位
int n,d;//相邻n位中不同的不能超过d种
class Node{
public:
	unsigned s;
	LDB f;
	int nxt;
};
class Hash_Map{
public:
	int head[HSIZE];
	Node lis[HSIZE];
	int tot;
	LDB& operator [] (unsigned s){
		int key=s%HSIZE,x;
		for(x=head[key];x;x=lis[x].nxt){
			if(lis[x].s==s) return lis[x].f;
		}
		lis[++tot]=(Node){s,-1,head[key]};//-1代表它不存在
		head[key]=tot;
		return lis[tot].f;
	}
};
Hash_Map F[51];
unsigned re_label(unsigned s){
	static int lis[10];
	memset(lis,0,sizeof(lis));
	int ans=0,tot=0;
	for(int i=0;i<32;i+=4){
		int t=(s>>i)&15;
		if(!t) break;
		if(!lis[t]) lis[t]=++tot;
		ans|=(lis[t]<<i);
	}
	return ans;
}
void calc_len(unsigned s,unsigned &len,unsigned &mx){
	len=mx=0;
	for(int i=0;i<32;i+=4){
		unsigned t=(s>>i)&15;
		if(!t) break;
		len++,mx=max(mx,t);
	}
}
LDB DP(unsigned s,int len){//在s之后还要走len位
	s=re_label(s);
	LDB &ans=F[len][s];
	if(ans>=0) return ans;
	ans=0;
	unsigned m,mx;
	calc_len(s,m,mx);
	if(mx>d) return ans=0;
	if(len==0) return ans=1;
	//考虑加上一个新的
	if(mx<d){
		if(m<n-1) ans+=(26-mx)*DP(s|((mx+1)<<m*4),len-1);
		else ans+=(26-mx)*DP((s>>4)|((mx+1)<<(n-2)*4),len-1);
	}
	//考虑用一个旧的
	for(unsigned i=1;i<=mx;i++){
		if(m<n-1) ans+=DP(s|(i<<m*4),len-1);
		else ans+=DP((s>>4)|(i<<(n-2)*4),len-1);
	}
	return ans;
}
unsigned turn_US(string &str){//若过长则只取后n-1位
	static int lis[26];
	int tot=0;
	memset(lis,0,sizeof(lis));
	int m=str.size(),start=max(0,m-(n-1));
	unsigned ans=0;
	for(int i=0;i<m-start;i++){
		int c=str[i+start]-'a';
		if(!lis[c]) lis[c]=++tot;
		ans|=(lis[c]<<i*4);
	}
	return ans;
}
bool check_legal(string &str){//检查一个字符串是否合法
	static int cnt[26];
	memset(cnt,0,sizeof(cnt));
	int now=0;
	for(int i=0;i<str.size();i++){
		int c=str[i]-'a';
		if(cnt[c]==0) now++;
		cnt[c]++;
		if(i>=n){
			c=str[i-n]-'a';
			cnt[c]--;
			if(cnt[c]==0) now--;
		}
		if(now>d) return false;
	}
	return true;
}
LDB calc(string str,int len){//以str为前缀,str后面还有len位的合法字符串数量
	if(!check_legal(str)) return 0;//如果str本身不合法
	unsigned s=turn_US(str);
	return DP(s,len);
}
LDB calc_less(string seed,int L){
	string now="";
	LDB ans=0;
	for(int i=0;i<L;i++){
		for(char c='a';c<seed[i];c++){
			ans+=calc(now+c,L-1-i);
		}
		now+=seed[i];
		if(!check_legal(now)) break;//这里测试时得取n位
		while(now.size()>=n) now.erase(now.begin());
	}
	return ans;
}
class NextHomogeneousStrings{
public:
	string getNext(int d_,int n_,string seed,LL K){
		K++;
		//找>=seed且第K小的字符串
		d=d_,n=n_;
		int L=seed.size();
		string ans;
		int left;
		for(int i=L-1;i>=0;i--){//试图在第i位上进行更改
			char low=(i==L-1?seed[i]:seed[i]+1);
			for(char c=low;c<='z';c++){
				LDB now=calc(seed.substr(0,i)+c,L-1-i);
				if(now<K) K-=now;
				else{
					ans=seed.substr(0,i)+c,left=L-1-i;
					goto OUT;
				}
			}
		}
		return "";
		OUT:;
		//现在我们需要取以ans为前缀的第K小字符串
		for(int i=1;i<=left;i++){
			for(char c='a';c<='z';c++){
				LDB now=calc(ans+c,left-i);
				if(now<K) K-=now;
				else{
					ans+=c;
					break;
				}
			}
		}
		return ans;
	}
};
int main(){
	freopen("homogeneous.in","r",stdin);
	freopen("homogeneous.out","w",stdout);
	NextHomogeneousStrings me;
	int d,n;
	LL k;
	string seed;
	cin>>d>>n>>seed>>k;
	cout<<me.getNext(d,n,seed,k)<<endl;
	//cout<<me.getNext(1,2,"aaa",3)<<endl;
	return 0;
}