【CTSC2016】香山的树

· · 题解

题面

写晕了写晕了，肝了一个下午加半个晚上，人都做懵了，幸亏BZOJ和UOJ都是跑最快的，不然感觉巨亏。

感觉思路不简单，代码也超级难写。

这题其实和【WC2004】孪生项链超级像，只不过这题代码更难写，也更恶心一点。

我们考虑数位DP。

怎么写DP？

从前往后扫描每个位置，从大到小枚举每个字符，计算以当前确定部分为前缀的方案总数。

那么如果方案总数>=k，说明这个位置不用弄了，直接进入下个位置。否则让k-=方案总数，去枚举下个字符。

接下来重点就是如何记录方案总数，想法当然就是之前提过的数位DP。

f[i][j][k]表示第i位已匹配的j位未匹配k位的方案总数。

枚举当前使用的字符，用KMP转移，由于已经知道了最大匹配长度，那么当前添加的字符就不能超过最大匹配的下一位。

事实上，已经确定的位置无需再计算方案总数，所以我们从未知的位置开始就行了。

而第i位的匹配情况只与第i-1位的匹配情况有关，所以这完全可以滚动一下。

具体转移以及各种细节参见代码吧。

code：

//2018.8.3 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register LL
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline LL read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline LL _abs(const res &x){
    return x>0?x:-x;
}
inline LL _max(const res &x,const res &y){
    return x>y?x:y;
}
inline LL _min(const res &x,const res &y){
    return x<y?x:y;
}
const LL C=30,CH=26,N=50+10;
const char max_char=CH+'a'-1;
LL n,k,len;
LL pre[N],next[N][C],minchar[N],ret[N];
LL f[2][N][N],dp[N][N];
char s[N<<1];
inline bool judge(){
    for(res i=0;i<len;i++)s[i+len]=s[i];
    for(res i=1;i<len;i++){
        res j;
        for(j=0;j<len;j++)if(s[j]!=s[i+j])break;
        if(j==len||s[i+j]<s[j])return 0;
    }
    return 1;
}
inline bool inc(){
    while(len&&s[len-1]==max_char)len--;
    if(!len)return 0;
    s[len-1]++;
    return 1;
}
inline LL get_tot(){
    memset(next[0],0,sizeof(next[0]));
    pre[0]=-1;
    minchar[0]=0;
    for(res i=0;i<len;i++){
        res c=s[i]-'a';
        if(c<minchar[i])return 0;
        minchar[i]=c;
        next[i][c]=i+1;
        if(pre[i]==-1)pre[i+1]=0;
        else pre[i+1]=next[pre[i]][c];
        minchar[i+1]=minchar[pre[i+1]];
        for(res j=0;j<CH;j++)next[i+1][j]=next[pre[i+1]][j];
    }
    for(res i=0;i<=len;i++){
        ret[i]=0;
        res j=i;
        for(res k=0;k<len;k++){
            if(s[k]-'a'<minchar[j]){ret[i]=-1;break;}
            j=next[j][s[k]-'a'];
            if(j==len)ret[i]++;
        }
    }
    memset(f,0,sizeof(f));
    memset(dp,0,sizeof(dp));
    f[len&1][pre[len]][0]=1;
    for(res i=len;i<=n;i++){
        memset(f[(i+1)&1],0,sizeof(f[(i+1)&1]));
        for(res j=0;j<len;j++)
            for(res k=0;k<=n-len;k++){
                if(ret[j]>=0)dp[i][k+ret[j]]+=f[i&1][j][k];
                if(i==n)continue;
                if(f[i&1][j][k]){
                    if(j+1==len)f[(i+1)&1][pre[len]][k+1]+=f[i&1][j][k];
                    else f[(i+1)&1][j+1][k]+=f[i&1][j][k];
                    f[(i+1)&1][0][k]+=f[i&1][j][k]*(CH-1-minchar[j]);
                }
            }
    }
    for(res i=pre[len];i;i=pre[i]){
        if(ret[len-i]>=0)
            for(res j=2;j*(len-i)<=n;j++)
                if(j*(len-i)>=len)dp[j*(len-i)][j]--;
        if((len-i)*2<len)i=(i-1)%(len-i)+1;
    }
    for(res i=len;i<=n;i++)
        for(res j=1;j<=i;j++)
            if(dp[i][j])for(res k=2;i*k<=n;k++)dp[i*k][j*k]-=dp[i][j];
    res ans=0;
    for(res i=len;i<=n;i++)
        for(res j=1;j<=i;j++)
            if(dp[i][j])ans+=dp[i][j]/j;
    return ans;
}
int main(){
    n=read(),k=read();
    scanf("%s",s);
    len=strlen(s);
    while(233){
        res tot=get_tot();
        if(tot<k){
            k-=tot;
            if(!inc()){puts("-1");return 0;}
        }
        else {
            if(judge())
                if(--k==0)break;
            s[len++]='a';
        }
    }
    for(res i=0;i<len;i++)putchar(s[i]);
    return 0;
}