先考虑这个权值 \(\sqrt[c]{\prod\limits_{i = 1}^c V_i}\)。
感觉找不到好的方法算出精确值，但是能发现只用比大小。
于是考虑取个对数成 \(\frac{1}{c}\times \ln(\prod\limits_{i = 1}^c V_i) = \frac{1}{c}\times (\sum\limits_{i = 1}^n\ln V_i)\)，因为 \(e > 1\) 所以大小关系不变。
于是用 \(\ln V_i\) 替换 \(V_i\)，最大值就是 \(\frac{\sum\limits_{i = 1}^c V_i}{c}\)。
能发现这变为了分数规划的模型，二分法解决。
考虑对于当前二分的答案 \(w\) 该怎么处理。
考虑到加一次这个串的贡献需满足这个串匹配上了，于是考虑建 \(\text{ACAM}\)。
同时维护一下节点 \(\text{fail}\) 跳上去所包含的节点的 \(V_i\) 的和记为 \(val_i\) 还有总覆盖次数 \(cnt_i\)，因为对于每一个 \(V\) 都要 \(-w\)，实际上这个节点的权值需要 \(-w\times cnt_i\)。
那就可以在 \(\text{ACAM}\) 上进行 \(\text{DP}\)。
定义 \(f_{i, j}\) 表示前 \(i\) 个字符目前在结点 \(j\) 的最大权值和。
考虑在第 \(i + 1\) 位填上字符 \(c\)（需合法）变为 \(k\) 状态，则转移为 \(f_{i + 1, k} = \max\{f_{i, j} + val_k\}\)。
输出方案只需在转移时记录下转移过来的节点和该位选取的数字即可。
时间复杂度 \(O(Tns)\)，\(T\) 为二分次数。
#include<bits/stdc++.h>
using d64 = long double;
const int maxn = 1.5e3 + 10, limw = 10;
int n;
int ch[maxn][limw], tot; d64 val[maxn]; int cnt[maxn], fail[maxn];
char S[maxn], T[maxn], E[maxn];
d64 f[maxn][maxn]; int lst[maxn][maxn], cr[maxn][maxn];
double solve(d64 v, bool flg = 0) {
for (int i = 0; i <= tot; i++) val[i] -= v * cnt[i];
for (int i = 0; i <= n; i++) for (int j = 0; j <= tot; j++) f[i][j] = -1e9;
f[0][0] = 0;
for (int i = 0; i < n; i++) for (int j = 0; j <= tot; j++) if (fabs(f[i][j] + 1e9) > 1e-4) {
for (int k = 0, v; k < 10; k++) if (S[i + 1] == '.' || S[i + 1] - '0' == k) {
d64 F = f[i][j] + val[v = ch[j][k]];
if (F > f[i + 1][v]) f[i + 1][v] = F, lst[i + 1][v] = j, cr[i + 1][v] = k;
}
}
for (int i = 0; i <= tot; i++) val[i] += v * cnt[i];
int u = 0;
for (int i = 1; i <= tot; i++) f[n][i] > f[n][u] && (u = i);
if (flg)
for (int i = n, j = u; i; j = lst[i--][j]) E[i] = '0' + cr[i][j];
return f[n][u];
}
int main() {
int m; scanf("%d%d%s", &n, &m, S + 1);
while (m--) {
d64 v;
scanf("%s%Lf", T + 1, &v), v = std::log(v);
int len = strlen(T + 1), now = 0;
for (int i = 1, c; i <= len; i++) {
! ch[now][c = T[i] - '0'] && (ch[now][c] = ++tot);
now = ch[now][c];
}
val[now] += v, cnt[now]++;
}
std::queue<int> q;
for (int i = 0, u; i < 10; i++) (u = ch[0][i]) && (q.push(u), 1);
while (! q.empty()) {
int u = q.front(); q.pop();
val[u] += val[fail[u]], cnt[u] += cnt[fail[u]];
for (int i = 0, v; i < 10; i++) (v = ch[u][i]) ? (fail[v] = ch[fail[u]][i], q.push(v), 1) : (ch[u][i] = ch[fail[u]][i]);
}
d64 l = 0, r = 21.0, ans = 0;
for (int Ts = 14; Ts; Ts--) {
d64 mid = (l + r) / 2.0;
solve(mid) > 0 ? (ans = mid, l = mid) : (r = mid);
}
solve(ans, 1); printf("%s", E + 1);
return 0;
}