Count The Repetitions
题面
定义 conn(s,n) 为 n 个字符串 s 首尾相接形成的字符串，例如：
conn(“abc”,2)=”abcabc”
称字符串 a 能由字符串 b 生成，当且仅当 a 为 b 的子序列。
例如 abdbec 可以生成 abc，但是 acbbe 不能生成 abc。
给定两个字符串 s1 和 s2，以及两个整数 n1 和 n2，求一个最大的整数 m，满足 conn(conn(s2,n2),m) 能由 conn(s1,n1) 生成。
s1 和 s2 长度不超过 100，n1 和 n2 不大于 \(10 ^ 6\)。
题解
我们可以转化一下，实际上就是要求一个最大的 \(m'\) 使得 \(conn(s_2, m_2)\) 能由 \(conn(s_1,n_1)\) 生成
暴力枚举的话，就是将 \(conn (s_1,n_1)\) 枚举一遍，能匹配上就匹配，时间复杂度为 \(O(T|s_1|n_1)\)
\(m'\) 可能很大，上界为 \(|s_1|n_1/|s_2|\) ，考虑将 \(m'\) 进行二进制拆分，那么我们可以将 \(conn(s_2,m')\) 看做若干个 \(conn(s_2,2^x)\) 相连的形式
我们可以求出 \(k \in [0,\log_2(|s_1|n1 / |s_2|)]\) ，从 \(conn(s_1,n_1)\) 的每个位置开始最少多长的字符串能拼出 \(2^k\) 个 \(s_2\)
但是 \(n_1\) 也非常大，不过因为 \(conn(s_1,n_1)\) 是由 \(s_1\) 重复 \(n_1\) 次得到的，所以只要没有到结尾，从 \(s_1[i]\) 开始和从 \(s_1[i + k|s_1|]\) 开始往后的字符是一样的，所以我们可以假设 \(n_1\) 无限大，然后只计算 \(i \le |s_1|\) 的从 \(s_1[i]\) 开始的位置即可
设 \(f(i,j)\) 表示从 \(s_1[i]\) 开始匹配到 \(2^j\) 个 \(s_1\) 最短需要多少个字符，我们只需预处理出 \(f(i,0)\) 即可，后面的可以递推得出
预处理 \(f(i,0)\) 暴力匹配即可，时间复杂度为 \(O(100^3)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;typedef long long ll;const int N = 110;int n1, n2;
char s1[N], s2[N];
ll f[N][32];void solve () {int sz = strlen (s1);//预处理 f[i][0]for (int i = 0; i < sz; i ++) {f[i][0] = 0;int p = i;for (int j = 0; j < (int)strlen (s2); j ++) {int cnt = 0;while (s1[p] != s2[j]) {p = (p + 1) % sz;cnt ++;if (cnt >= sz) {cout << 0 << endl;return;}}p = (p + 1) % sz;f[i][0] += cnt + 1;}}//计算出 f[i][j]for (int j = 1; j <= 30; j ++) {for (int i = 0; i < sz; i ++) {f[i][j] = f[i][j - 1] + f[(i + f[i][j - 1]) % sz][j - 1];}}//计算答案ll res = 0, p = 0, t = 0;for (int j = 30; j >= 0; j --) {if (p + f[p % sz][j] <= n1 * sz) {p += f[p % sz][j];t += (1 << j);}}res = max (res, t);cout << res / n2 << endl;
}int main () {while (~scanf ("%s%d%s%d", s2, &n2, s1, &n1)) {solve ();}return 0;
}