躺在床上睡不着，想这个题，突然有了一个对的思路，把自己吓醒
思维过程
首先我们要考虑的是，假设 \(s\) 已知，Appleman 的策略是什么
我们发现他的策略非常简单，就是能匹配就继续匹配，直到不能再匹配了，才划分一下
道理也很简单，现在不划进来，没有任何好处：这不会让后面划的更少，甚至可能更多。
现在我们考虑 Toastman，由于我们已经知道了 Appleman 的策略，我么就要根据他的策略，来卡他
考虑一个一个加入字符。每次加入，Appleman都会试着匹配一下，如果还是子串，就纳入原来划的串；如果失配了，就新划一个串出来，把这个字符加入新划的串。
我们要让它划的尽量多，就要尽快失配，也就是尽快的找一个不是 \(t\) 子串的串。什么影响了我们的决策？显然，第一个字符肯定有影响：对于每个字符，要达到失配状态需要的步数是不同的。我们称它为 “入”，就是如何 进入 了当前划的串。
如 t="AAABACADBABBBCBDCACBCCCDDDBDCDD" 的时候，如果是 A 开头，需要 "AAB"，三步才能失配；但如果是 D 开头，只用 “DA"，两步就能失配。
那我们也不能不管后面，所以我们要知道我们是加了哪个字符时候失配的，对应的称为”出“。
比如刚才 "AAB" 串的 “出” 就是字符 B，原本 AA 还能匹配，加入这个 B 完了就匹配不上，需要新划一个串来
显然，一个串的“出”就是下一个串的“入”，因此我们可以一个接一个的搞，跳着 贪心，来为难这个 Appleman。
如果我们已知了 ”入“ 和 ”出“，接下来策略很明显，只要让中间的串最短就行了。设入为 \(a\)，出为 \(b\)，记这个最短的长度为 \(f(a,b)\)。形式化的说就是，找到一个串 \(t'\) 使得它开头为 \(a\) 结尾为 \(b\)，不是 \(t\) 的子串，且长度尽量短，此时 \(f(a,b)=|t|-1\)。而我们可以，也需要，把这个 \(f\) 预处理出来。
为啥 需要 预处理：有了这个 \(f\)，我们就不需要逐个字符的考虑贪心，可以“跳着”贪心，并且对于相同的问题（“入”相同，“出”相同，认为是相同的问题）可以直接用 \(f\) 解决，不再需要每次求了。而且这个 \(f\) 只占用 \(16\) 个空间，能够轻易存下来。
要求解这个 \(f\)， 就把 SAM 建出来，枚举 \(a,b\) ，然后找到没有 \(b\) 出边的所有点，处理一下每个点到它们的最短路即可。
优化：由于 \(|s|\le 10^{18}\)，而 \(4^{30}>10^{18}\)，所以只要长度到 \(30\)，就一定能失配。
所以我们并不需要写 SAM，把每个长度 \(\le 30\) 的子串搞到一个 Trie 里就行了
然后我们继续考虑 Toastman 的策略：假设我们预先知道了划分出来的子串要有 \(k\) 个，开头是 \(c_1,c_2...c_k\)，那么 \(s\) 的长度至少为 \(f(c_1,c_2)+f(c_2,c_3)...+f(c_{k-1},c_k)+1\) （这里的 \(1\) 是留给最后一个串，它至少要有一个字母，这个字母就是 \(c_k\)）。如果这个东西 \(\le n\)，那么划出来 \(k\) 个就可行。
我们发现，这个 \(f\) 我们需要“接连的”用里面的东西，于是我们把它看成一张图：\(f(a,b)\) 表示 \(a\) 到 \(b\) 的边权，那么上面这个式子就变成了一个从 \(c_1\) 到 \(c_k\) 的路径，途径 \(k-1\) 条边，可以任意经过点任意次。
现在我们相当于要求一个 \(4\) 个点的图上走 \(k-1\) 条边的权值和的最小值。这个是经典题，把 floyd 的转移看成矩阵乘法，然后把原图的邻接矩阵求出 \(k-1\) 次幂，然后找到最小值就行了。
然后我们的思路就是，二分这个 \(k\) ，然后拿矩阵快速幂判断是否行。
思路总结
感觉这个题的核心在于这个 \(f\)。\(f\) 干了两个事情，
- 找到了问题的本质 （“入”和“出”）
- 把本质相同的问题一块处理 （长度直接就是 \(f(a,b)\)，加上就完了，具体是啥看都不看）
而且这个 \(f\) 还有一个很好的性质，它可以持久化发展，能够一个接一个的贪心。并且，有了这个 \(f\) 之后，就是顺理成章的建图→快速幂→二分...这个题便迎刃而解。可以说，把 \(f\) 想出来，这题就没了。
代码
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
#define N 200005
#define ll long long
#define F(i,l,r) for(int i=l;i<=r;++i)
#define D(i,r,l) for(int i=r;i>=l;--i)
#define Fs(i,l,r,c) for(int i=l;i<=r;c)
#define Ds(i,r,l,c) for(int i=r;i>=l;c)
#define MEM(x,a) memset(x,a,sizeof(x))
#define FK(x) MEM(x,0)
#define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))
#define p_b push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define iter(a,p) (a.begin()+p)
int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
template <typename T> void Rd(T& arg){arg=I();}
template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}
ll len;
int n; char t[N];
void Input()
{
scanf("%lld",&len); // 题目里给的n，然而我这里的 n=|t|，就管它叫 len，即 |s|
scanf("%s",t+1); n=strlen(t+1);
}
class Trie
{
public:
#define M 3000006 // 30n
int ch[M][4]; int tot;
char dep[M];
Trie() {FK(ch); tot=1;}
void ins(char *s)
{
int cur=1; char *p=s;
for(int i=1;i<=30 and (*p);++i,++p) // 这里到 30 就行了
{
int c=(*p)-'A';
if (!ch[cur][c]) ch[cur][c]=++tot;
cur=ch[cur][c]; dep[cur]=i;
}
}
char mark[M]; // 每个节点属于根节点哪个儿子(0~3)的子树
int near[4][4];
void DFS_mark(int u,int f) // f:0~3
{
mark[u]=f;
F(i,0,3) if (ch[u][i]) DFS_mark(ch[u][i],f);
}
void sakuya()
{
F(i,0,3) DFS_mark(ch[1][i],i);
MEM(near,0x3f);
F(j,0,3)
{
F(i,1,tot) if (!ch[i][j]) // 这个点没有 j 的转移
{
near[mark[i]][j]=min(near[mark[i]][j],(int)dep[i]);
// 找到这个点的路径上第一个字符是啥
// 然后这个字符就是 "入", j就是“出”
}
}
}
}T;
template<const int S> class Matrix
{
public:
ll a[S][S];
Matrix<S>() {MEM(a,0x3f);}
ll* operator[](int i) {return a[i];}
};
template<const int S> Matrix<S> operator*(Matrix<S> a,Matrix<S> b)
{
Matrix<S> c; MEM(c.a,0x3f);
F(i,0,S-1) F(j,0,S-1) F(k,0,S-1) c[i][k]=min(c[i][k],a[i][j]+b[j][k]); // 类似 floyd 的转移
return c;
}
template<const int S> Matrix<S> operator^(Matrix<S> a,ll p)
{
Matrix<S> r; F(i,0,S-1) r[i][i]=0;
while(p)
{
if (p&1ll) r=r*a;
a=a*a; p>>=1ll;
}
return r;
}
Matrix<4> f;
// f[a][b]: 开头为a的串, 要以b跳出自动机, 最短串长
// 形式化的说, 找到一个最短的串s, 使得s第一个为a最后一个为b, s不是t子串, f[a][b]=|s|-1
bool cxk(ll mid)
{
// f可以看做贪心过程中, 从一个字母转移到另一个字母所需的最小长度 (<=30)
// 然后 f^(mid-1) 就是走 mid-1 步 (必定划分成了mid个串) 所需的长度
// 看是否存在长度<=len的方案即可, 若有, 则至少mid个串; 无则<mid个串
Matrix<4> fn=(f^(mid-1));
F(i,0,3) F(j,0,3) if (fn[i][j]<len) return true; // 留下一个位置给最后那个字母 (j)
return false;
}
void Sakuya()
{
F(i,1,n) T.ins(t+i);
T.sakuya();
F(a,0,3) F(b,0,3)
{
f[a][b]=T.near[a][b];
}
ll Low=1,High=len;
while(Low<High)
{
ll mid=(Low+High+1)>>1;
if (cxk(mid)) Low=mid;
else High=mid-1;
}
printf("%lld\n",Low);
}
void IsMyWife()
{
Input();
Sakuya();
}
}
#undef int //long long
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();
return 0;
}