F题解知识点：枚举，前缀和，数论 。
注意到一个数字 \(\mod 9\) 的答案和所有数位加起来 \(\mod 9\) 的答案相同，因此先对 \(s\) 数位预处理模意义前缀和 。
然后处理出所有 \(w\) 长度的串的余数，把串首坐标放进桶中对应余数的位置，只需要存两个最左边的即可 。
对于每组询问，遍历余数 \(a,b\) 满足 \(a \cdot re + b \equiv k \pmod 9\)，其中 \(re\) 为 \([l,r]\) 的余数 。将余数 \(a,b\) 对应的串下标更新一下答案即可，答案可以用 pair存，方便更新 。注意特判 \(a = b\) 的情况，需要同一个余数的前两个下标 。
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007];bool solve() {string s;cin >> s;int n = s.length();s = "?" + s;for (int i = 1;i <= n;i++) a[i] = (s[i] - '0' + a[i - 1]) % 9;int w, m;cin >> w >> m;vector<vector<int>> pos(9);for (int i = w;i <= n;i++) {int re = (a[i] - a[i - w] + 9) % 9;if (pos[re].size() < 2) pos[re].push_back(i - w + 1);}while (m--) {int l, r, k;cin >> l >> r >> k;int re = (a[r] - a[l - 1] + 9) % 9;pair<int, int> ans = { n + 1,n + 1 };for (int i = 0;i <= 8;i++) {if (pos[i].empty()) continue;for (int j = 0;j <= 8;j++) {if (pos[j].empty()) continue;if ((i * re + j) % 9 == k) {if (i != j) ans = min(ans, { pos[i][0],pos[j][0] });else if (i == j && pos[i].size() == 2) ans = min(ans, { pos[i][0],pos[i][1] });}}}if (ans > pair<int, int>{n, n}) cout << -1 << ' ' << -1 << '\n';else cout << ans.first << ' ' << ans.second << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}G题解知识点：线性dp 。
预处理出 \(s\) 中所有能删除 \(t\) 的下标，暴力 \(O(n^2)\) 处理即可，存进 vector。随后dp一下前 \(i\) 个能删除位置的最小删除次数 。
设 \(f[i]\) 为考虑到第 \(i\) 个能删除的位置，删除 \([1,v[i]]\) 所有能删除的段，且一定删除第 \(i\) 段的最小删除次数 。设 \(tot[i]\) 为能够达成 \(f[i]\) 删除次数的对应的方案数 。
对于 \(v[i]\)，我们枚举上一个删除的位置 \(v[j]\)，先保证 \(i,j\) 不重合即 \(v[i]-v[j]\geq m\)，然后保证 \(i,j\) 中间没有别的能删除的段即 $v[k] - v[j] < m $ 以及 $ v[i] - v[k] < m$。于是可以转移：
if (f[i] > f[j] + 1) { f[i] = f[j] + 1; tot[i] = tot[j];}else if (f[i] == f[j] + 1) { tot[i] = (tot[i] + tot[j]) % mod;}最后统计末尾重合的一段的最小删除次数，以及对应的总方案数 。
时间复杂度 \(O(nm^2)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;const int mod = 1e9 + 7;bool solve() {string s, t;cin >> s >> t;int n = s.size(), m = t.size();s = "?" + s;vector<int> v;v.push_back(0);for (int i = m;i <= n;i++)if (s.substr(i - m + 1, m) == t) v.push_back(i);vector<int> f(507, 0x3f3f3f3f), tot(507, 0);f[0] = 0, tot[0] = 1;for (int i = 1;i < v.size();i++) {for (int j = i - 1;j >= 0;j--) {if (v[i] - v[j] < m) continue;bool ok = 1;for (int k = j + 1;k < i;k++) ok &= v[k] - v[j] < m || v[i] - v[k] < m;if (!ok) break;if (f[i] > f[j] + 1) {f[i] = f[j] + 1;tot[i] = tot[j];}else if (f[i] == f[j] + 1) {tot[i] = (tot[i] + tot[j]) % mod;}}}int mi = n, ans = 0;for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m) mi = min(mi, f[i]);for (int i = 0;i < v.size();i++) if (v.back() - v[i] < m && f[i] == mi) ans = (ans + tot[i]) % mod;cout << mi << ' ' << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}