题意
有两个字符串 $s,t$，有一个人在玩游戏。他的目标是凑出串 $s$。初始他有一个空串，每次可以找出 $t$ 的一个子串接到这个串的后面，他会最小化他的操作。
现在你想找到这样一个长度为 $n$ 的串 $s$，使得他需要的操作次数尽量大。$n \leq 10^{18},1 \leq |t| \leq 10^5$。
题解
显然先手每次都是暴力找到最长的能和当前这个后缀匹配的 $t$ 的子串然后贪心匹配。所有第一步取的比它段的操作都可以相同步数地转化成第一步取最长的操作（因为是否是一个串的子串具有单调性）。
做法 1
看到子串问题，首先想到建立 SAM，这样求某个确定的 $s$ 串的最小操作次数，只需要从 SAM 开始走，如果走到某个状态后想走字符 $c$ 结果不能接着走了，就跳到 $rt$ 的 $c$ 边指向的儿子，代表必须选一次串。答案就是跳的次数加一。
那么我们可以将所有这种可能失配的「过程」，都变成一条连向对应位置，代价为 $1$ 的边；原 SAM 上的边代价都是 $0$。问题就转化成：你可以走最多 $n$ 步，要求走到的权值和尽量大。
由于 SAM 太大了，直接 dp 不太现实。所以我们要反过来看问题，思考能否去从答案的角度入手。假设我们想检查答案 $r$ 是否可能达到，相当于就是要求走 $r$ 次 $1$ 边，问走过的最短可能路径，如果 $n$ 比它小显然不可能。虽然这并不是充要的，但是我们如果能找到最大的满足这个条件的 $r$，那么这个 $r$ 一定是满足条件的答案。
现在只需要关心 $1$ 边的经过次数，我们就可以缩点了，我们只需要关心根的儿子之间的互相转化关系，所以我们预处理 $A_{i,j}$，表示 $i$ 通过一次 $1$ 边走到 $j$ 的最短路（可以 bfs 预处理，这里注意 SAM 是个 DAG，所以每次 bfs 前都要清空）。然后设 $f_{i,j}$ 表示经过 $i$ 次 $1$ 边，当前在点 $j$ 的最小可能长度，转移就是：
$$ f_{i,j} = \min_k f_{i-1,k}+A_{k,j} $$
然后就可以倍增求 $f$ 了。我们用类似倍增的方法，倒着枚举，每次转移上去一个 $f_{2^i}$，看看是否超过了 $n$ 的限制，如果没超就保留。
做法 2
发现我们贪心的思路一定是每次放进去一个恰好不是 $t$ 的子串的串，但是这个「恰好」就意味着后面要多一个不确定的字符，这里就不太好直接贪心了。
那么我们可以考虑 dp：设 $f_{l,r}$ 表示左边字符是 $l$，右边字符是 $r$ 的方案数，合并两个状态我们只需要保证左边的状态的结尾和右边状态的开头相同就好了，这个也是可以倍增做的。
现在目标就是求出放一次的每种情况的长度最小值。可以直接暴力枚举。因为我们有用的串一定不是 $t$ 的子串，而这个随着长度的增长是指数级别的，枚举到 $O(\log n)$ 长度就可以了。
代码
我写的是做法 1。
#include <bits/stdc++.h>
#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e5 + 5;
const LL MAX = 4e18;
LL n;
char s[MAXN];
int ch[MAXN][4],len[MAXN],fail[MAXN],tot=1;
inline int work(int p,int c){
int q = ch[p][c],nq = ++tot;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
len[nq] = len[p]+1;fail[nq] = fail[q];
fail[q] = nq;
for(;p&&ch[p][c]==q;p=fail[p]) ch[p][c] = nq;
return nq;
}
inline int insert(int p,int c){
int q = ch[p][c];
if(q){
if(len[q] == len[p]+1) return q;
return work(p,c);
}
int np = ++tot;len[np] = len[p]+1;
for(;p&&!ch[p][c];p=fail[p]) ch[p][c] = np;
if(!p) fail[np] = 1;
else{
q = ch[p][c];
if(len[q] == len[p]+1) fail[np] = q;
else fail[np] = work(p,c);
}
return np;
}
LL A[5][5];
bool vis[MAXN];
int dis[MAXN];
inline void gao(int v,int now){
std::queue<int> q;q.push(v);vis[v] = 1;dis[v] = 1;
while(!q.empty()){
int v = q.front();q.pop();
FOR(i,0,3){
if(ch[v][i]){
if(!vis[ch[v][i]]) q.push(ch[v][i]),vis[ch[v][i]] = 1,dis[ch[v][i]] = dis[v]+1;
}
else{
A[now][i+1] = std::min(A[now][i+1],(LL)dis[v]);
}
}
}
}
struct Matrix{
LL a[5][5];
Matrix operator * (const Matrix &t){
Matrix res;
FOR(i,1,4){
FOR(j,1,4){
res.a[i][j] = 4e18;
FOR(k,1,4){
res.a[i][j] = std::min(res.a[i][j],a[i][k]+t.a[k][j]);
if(res.a[i][j] > 4e18) res.a[i][j] = 4e18;
}
}
}
return res;
}
}pw[60];
inline LL calc(Matrix A){
LL res = 4e18;
FOR(i,1,4) FOR(j,1,4) res = std::min(res,A.a[i][j]);
return res;
}
int main(){
scanf("%lld%s",&n,s+1);int len = strlen(s+1);
int p = 1;FOR(i,1,len) p = insert(p,s[i]-'A');
FOR(i,1,4) FOR(j,1,4) A[i][j] = 4e18;
FOR(i,0,3) if(ch[1][i]) CLR(vis,0),gao(ch[1][i],i+1);// 注意这是个dag，需要清空
--n;
FOR(i,1,4) FOR(j,1,i-1) std::swap(A[i][j],A[j][i]);
FOR(i,1,4) FOR(j,1,4) pw[0].a[i][j] = A[i][j];
FOR(i,1,59) pw[i] = pw[i-1]*pw[i-1];
Matrix now;LL ans = 0;
FOR(i,1,4) FOR(j,1,4) now.a[i][j] = i==j?0:4e18;
// FOR(i,1,4) FOR(j,1,4) printf("%lld%c",pw[0].a[i][j]," \n"[j==4]);
ROF(i,59,0){
Matrix tmp = now*pw[i];
if(calc(tmp) > n) continue;
now = tmp;ans |= (1ll<<i);
}
printf("%lld\n",ans+1);
return 0;
}