题目传送门：。
题意简述：
有一个长度为 \(n\) 的母串，其中某些位置已固定，另一些位置可以任意填。
同时给定 \(m\) 个小串，第 \(i\) 个为 \(S_i\)，所有位置都已固定，它的价值为 \(V_i\)。
每次每个小串在母串中出现一次，便会给答案的多重集贡献一个 \(V_i\)。
最终的答案为多重集的几何平均数，定义空集的几何平均数为 \(1\)。
请你求出一个合法母串（往可以填的位置填合法字符）使得答案最大。
\(1\le n,s\le 1501\)，\(1\le V_i\le \max V=10^9\)，其中 \(\displaystyle s=\sum_{i=1}^{m}|S_i|\)。
题解：
假设多重集的大小为 \(c\)，第 \(i\) 个元素为 \(w_i\)，则 \(\displaystyle\mathrm{Ans}=\sqrt[c]{\prod_{i=1}^{c}w_i}\)。
两边取对数，有 \(\displaystyle\ln\mathrm{Ans}=\frac{1}{c}\sum_{i=1}^{c}\ln w_i\)，转化为经典的 0/1 分数规划问题。
二分答案，若等式右边大于 \(\mathrm{mid}\)，则有：
\(\begin{aligned}\frac{1}{c}\sum_{i=1}^{c}\ln w_i&>\mathrm{mid}\\\sum_{i=1}^{c}\ln w_i&>c\cdot\mathrm{mid}\\\sum_{i=1}^{c}(\ln w_i-\mathrm{mid})&>0\end{aligned}\)
所以，建出小串的 AC 自动机，然后二分答案后在 AC 自动机上 DP 判断不等式是否满足。
DP 时每个小串的权值设为 \(\ln V_i-\mathrm{mid}\)，注意要记录最佳转移点，以输出方案。
下面是代码，复杂度 \(\mathcal{O}(s\Sigma(\log\max V-\log\epsilon))\)：
#include#include typedef double f64;const int MN = 1505, Sig = 10;const f64 eps = 1e-6, inf = 1e99;int N, M;char T[MN];char str[MN];int ch[MN][Sig], fail[MN], sum[MN], cnt;f64 val[MN];inline void Insert(char *s, f64 v) { int now = 0; for (; *s; ++s) { if (!ch[now][*s & 15]) ch[now][*s & 15] = ++cnt; now = ch[now][*s & 15]; } ++sum[now], val[now] += v;}int que[MN], l, r;void BuildAC() { fail[0] = -1; que[l = r = 1] = 0; while (l <= r) { int u = que[l++]; for (int i = 0; i < Sig; ++i) { if (ch[u][i]) { int x = fail[u]; while (~x && !ch[x][i]) x = fail[x]; if (~x) fail[ch[u][i]] = ch[x][i]; que[++r] = ch[u][i]; } else if (~fail[u]) ch[u][i] = ch[fail[u]][i]; } } for (int i = 2; i <= r; ++i) sum[que[i]] += sum[fail[que[i]]], val[que[i]] += val[fail[que[i]]];}f64 f[MN][MN];int g[MN][MN][2];char AT[MN];inline f64 DP(f64 V) { for (int j = 0; j <= cnt; ++j) val[j] -= sum[j] * V; for (int i = 0; i <= N; ++i) for (int j = 0; j <= cnt; ++j) f[i][j] = -inf; f[0][0] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= cnt; ++j) { if (f[i][j] == -inf) continue; if (T[i] == '.') { for (int k = 0; k < Sig; ++k) { int _j = ch[j][k]; if (f[i + 1][_j] < f[i][j] + val[_j]) f[i + 1][_j] = f[i][j] + val[_j], g[i + 1][_j][0] = j, g[i + 1][_j][1] = k; } } else { int _j = ch[j][T[i] & 15]; if (f[i + 1][_j] < f[i][j] + val[_j]) f[i + 1][_j] = f[i][j] + val[_j], g[i + 1][_j][0] = j, g[i + 1][_j][1] = T[i] & 15; } } } for (int j = 0; j <= cnt; ++j) val[j] += sum[j] * V; int ans = 0; for (int j = 1; j <= cnt; ++j) if (f[N][j] > f[N][ans]) ans = j; for (int i = N, j = ans; i >= 1; --i) AT[i - 1] = g[i][j][1] | 48, j = g[i][j][0]; return f[N][ans];}int main() { scanf("%d%d", &N, &M); scanf("%s", T); for (int i = 1; i <= M; ++i) { f64 v; scanf("%s%lf", str, &v); Insert(str, log(v)); } BuildAC(); f64 l = 0, r = log(1e9 + 5), mid, ans = 0; while (r - l > eps) { mid = (l + r) / 2; if (DP(mid) > 0) ans = mid, l = mid; else r = mid; } DP(ans); printf("%s\n", AT); return 0;}