题解 CF461E 【Appleman and a Game】

· · 题解

orz原题解，看了很久才看懂。。。其实原题解的步骤很清晰，只是对于我这种弱菜而言还是有些地方要想很久才能想明白为什么。。。于是写了个（似乎）比较详细的题解。

考虑Appleman所采取的最优策略是什么样的。

假设当前已经填了i-1个字符，找到t中最长的满足s[i,i+len-1]=t[pos,pos+len-1]的子串填进去，其中pos是子串的左端点，len是子串的长度。

这是因为，如果一直填短串，相当于到了最后还要比填长串的多填几个才能填到n。 如果先填短串，然后在某一步填长串，最多也只能和之前的变成一样的长度，不可能比一直填长串的长。（可以画图理解一下）

然后就可以来做题了。

题目要求最小值最大，发现当可以用较小步数填时显然比它大的步数也都可以，满足二分性质，于是可以二分答案。

设dp[x][i][j]表示填x次，第x次填进去的子串开头的字母是i，第x+1次填进去的子串开头的字母是j，所能填出的最小长度。（j不被计算在长度中）

当dp[x][i][j]<n时，即采用这种t，即使Appleman用了最优填法也只能在还没到n的时候就用完了x次，剩下的长度需要的步数为正，即答案>x；反之，答案小于等于x。

初始：dp[1][i][j]相当于找到一个长度为L的子串，使得它在t中出现的长度是L-1，那么最小的L-1就是dp[1][i][j]。

然而这并不好找，于是我们思考一下，发现显然地，dp[1][i][j]其实就是最小的以i开头，j结尾且不是t的子串的最短字符串的长度。

于是我们可以从小到大枚举长度L，找出t中有多少种（注意不是“个”）不同的以i开头，j结尾且长度为L的子串（数量记为calc[i][j][L]）， 假设字符集大小是C，如果calc[i][j][L]=C^(L-2)，就继续往下枚举，不然就让dp[1][i][j]=L-1并break。因为要求子串本质不同，那就用字典树统计。

然而这样还是不行，因为L<=|t|<=1e5，这样会T飞。

于是再仔细思考一下，显然我们只有当calc[i][j][L]>=pw(C,L-2)时才不合法，而calc[i][j][L]恒<=|t|，即|t|>=calc[i][j][L]>=pw(C,L-2)，即L<=logC_|t|+2时才不合法。

换而言之，L最大不超过logC_|t|+3。 这样一来，直接按照之前说的方法做就可以了。

转移：dp[x+1][i][j]=min(dp[x][i][k]+dp[1][k][j]) (0<=k<=C-1)

由于1<=x<=n而n<=1e18，可以矩阵乘法+快速幂。

问题解决辣，复杂度是O(|t|logC_|t|+((C^3)(log^2 n)))的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(register int x=y; x<=z; x++)
#define downrep(x,y,z) for(register int x=y; x>=z; x--)
#define LL long long
#define repedge(x,y) for(register int x=hed[y]; ~x; x=edge[x].nex)
#define ms(x,y,z) memset(x,y,sizeof(z))
inline int read(){
    int x=0; int w=0; char ch=0;
    while(ch<'0' || ch>'9') w|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w? (-x):x;
}
const int N=100005;
const int C=4;
const int L=15;
LL n;
int m,calc[C][C][L],DEP,tr[N*L][C],nw[N*L],cnt;
char s[N];
struct mat{ LL num[C][C]; }B;
LL PW(LL a,LL b){
    LL res=1;
    while(b){ if (b&1) res=res*a; a=a*a; b>>=1; }
    return res;
}
void insert(int x){
    int k=0; int u=s[x]-'A';
    rep(i,x,min(m-1,x+DEP-1)){
       int p=s[i]-'A';
       tr[k][p]=tr[k][p]? tr[k][p]:(tr[k][p]=++cnt);
       k=tr[k][p];
       if (!nw[k]){ nw[k]=1; ++calc[u][p][i-x+1]; }
    }
}
mat operator * (mat a,mat b){
    mat c; rep(i,0,C-1) rep(j,0,C-1) c.num[i][j]=n+1ll;
    rep(k,0,C-1) rep(i,0,C-1) rep(j,0,C-1)
    c.num[i][j]=min(c.num[i][j],a.num[i][k]+b.num[k][j]);
    return c;
}
mat pw(mat a,LL b){
    mat res=a; b-=1ll;
    while(b){ if (b&1) res=res*a; a=a*a; b>>=1; }
    return res;
}
int check(LL x){
    mat res=pw(B,x); int pd=0;
    rep(i,0,C-1) rep(j,0,C-1)
    pd|=(res.num[i][j]<n);
    return pd;
}
LL solve(){
    LL l=1; LL r=n;
    while(l<r){
       LL mid=((l+r)/2ll);
       if (check(mid)) l=mid+1;
       else r=mid;
    }
    return l;
}
int main(){
    scanf("%lld",&n); scanf("%s",&s);
    m=strlen(s); DEP=min(11,m+1);
    rep(i,0,m-1) insert(i);
    rep(i,0,C-1) rep(j,0,C-1) downrep(k,DEP,2)
    if (calc[i][j][k]!=PW(C,k-2)) B.num[i][j]=k-1;
    printf("%lld\n",solve());
    return 0;
}