题意理解

我们有一个长度为 n 的宝石串 T，其中 0-9 表示宝石种类，. 表示残缺需要填补。
有 m 种咒语 (S_i, V_i)，当宝石串中出现一次 S_i 作为连续子串时，神力值 Magic 就乘以 V_i。
最终神力值 = Magic^(1/c)，其中 c 是咒语出现的总次数（不同位置算多次）。
如果 c=0，最终神力值为 1。

目标：填补所有 .，使得最终神力值最大，输出任意一个可行解。

关键点分析

1. 神力值公式
   初始 Magic = 1，每出现一次咒语 S_i 就乘 V_i。
   最终神力值 = Magic^(1/c)。
   取对数更好处理：
   设 log(Magic) = sum(出现次数 * log(V_i))，
   最终神力值取对数 = (sum(出现次数 * log(V_i))) / c。

   我们要最大化这个平均值。

2. 问题转化
   可以看作：在宝石串上，每个位置可能触发多个咒语（即某些咒语的串匹配到这里结束），我们要选择填补方案，使得 平均每次咒语触发的收益 最大。

   这是一个带权匹配数最大化平均值的问题，类似 0-1 分数规划。

3. 匹配计算
   给定一个完整的宝石串，我们可以用 AC 自动机统计所有咒语出现次数，并计算总收益。
   但这里宝石串未确定，我们需要决定每个 . 填什么数字。

4. 数据范围
   n ≤ 1501, s ≤ 1501，所以我们可以设计一个 O(n * s) 的动态规划。

思路

1. 构建 AC 自动机

将所有咒语串 S_i 插入 AC 自动机，并在每个终止节点记录 log(V_i) 的累加（因为一个节点可能对应多个咒语串结束，要全加上）。

2. 分数规划

假设我们猜测一个平均值为 x，那么问题变成：是否存在一种填法，使得
总收益 - x * 匹配次数 >= 0
即 sum( (log(V_i) - x) * 出现次数 ) >= 0。

于是我们把每个咒语的权值设为 log(V_i) - x，在 AC 自动机上走，每匹配到一个咒语就加上这个权值。

3. DP 设计

令 dp[i][u] 表示处理完前 i 个宝石，当前在 AC 自动机节点 u，能获得的最大 总收益 - x * 匹配次数。

转移：

• 如果 T[i] 是数字，直接沿 AC 自动机走到 v，加上 v 节点的权值和（即该节点所有咒语的 (log(V) - x) 之和）。
• 如果 T[i] 是 .，枚举填 0-9，同样走 AC 自动机，加上节点权值和。

初始：dp[0][0] = 0，其余为 -inf。

最终如果 max_u dp[n][u] >= 0，说明平均值 x 可行。

4. 二分答案

二分 x，范围 [0, max(log(V_i))]。
检查可行性后，我们还需要记录方案：在 DP 时记录从哪个状态转移过来，以及填了什么数字。

复杂度

• 二分次数约 O(log(1e9)) ≈ 30
• 每次 DP: O(n * 节点数)，节点数 ≤ s+1 ≤ 1501
  所以总复杂度 O(30 * n * s) 可过。

实现细节

• 用 double 存对数，避免精度问题（题目 V_i 最大 1e9，对数最大 ~20.7，不会溢出）。
• 记录方案时，为了避免重复记录，可以在 DP 时记录前驱状态和选择数字，最后回溯。
• 注意 AC 自动机构建时，fail 树上的权值要累加（因为 fail 指针指向的是当前串的最长后缀，如果该后缀也是某个咒语，也要算上匹配）。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1505;
const int MAXS = 1505;
const double INF = 1e18;
const double EPS = 1e-8;

int n, m;
string T;
string S[MAXN];
int V[MAXN];

int ch[MAXS][10], fail[MAXS], idx;
double val[MAXS];

void insert(string s, double w) {
    int p = 0;
    for (char c : s) {
        int u = c - '0';
        if (!ch[p][u]) ch[p][u] = ++idx;
        p = ch[p][u];
    }
    val[p] += w;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 10; i++) {
        if (ch[0][i]) q.push(ch[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        val[u] += val[fail[u]]; // fail 树上累加权值
        for (int i = 0; i < 10; i++) {
            if (ch[u][i]) {
                fail[ch[u][i]] = ch[fail[u]][i];
                q.push(ch[u][i]);
            } else {
                ch[u][i] = ch[fail[u]][i];
            }
        }
    }
}

double weight[MAXS];
double dp[MAXN][MAXS];
pair<int, int> pre[MAXN][MAXS];

bool check(double x) {
    for (int i = 0; i <= idx; i++) {
        weight[i] = val[i] - x; // 每个节点的权值
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= idx; j++) {
            dp[i][j] = -INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int u = 0; u <= idx; u++) {
            if (dp[i][u] < -1e9) continue;
            if (T[i] != '.') {
                int d = T[i] - '0';
                int v = ch[u][d];
                double nv = dp[i][u] + weight[v];
                if (nv > dp[i+1][v]) {
                    dp[i+1][v] = nv;
                    pre[i+1][v] = {u, d};
                }
            } else {
                for (int d = 0; d < 10; d++) {
                    int v = ch[u][d];
                    double nv = dp[i][u] + weight[v];
                    if (nv > dp[i+1][v]) {
                        dp[i+1][v] = nv;
                        pre[i+1][v] = {u, d};
                    }
                }
            }
        }
    }
    for (int u = 0; u <= idx; u++) {
        if (dp[n][u] >= 0) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    cin >> T;
    for (int i = 0; i < m; i++) {
        cin >> S[i] >> V[i];
    }

    // 建 AC 自动机
    idx = 0;
    memset(ch, 0, sizeof(ch));
    memset(val, 0, sizeof(val));
    double maxlog = 0;
    for (int i = 0; i < m; i++) {
        double w = log(V[i]);
        insert(S[i], w);
        maxlog = max(maxlog, w);
    }
    build();

    // 二分
    double l = 0, r = maxlog;
    for (int iter = 0; iter < 50; iter++) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    // 重建方案
    check(l);
    int u = 0;
    for (int v = 0; v <= idx; v++) {
        if (dp[n][v] >= 0) {
            u = v;
            break;
        }
    }
    string ans = "";
    for (int i = n; i > 0; i--) {
        int d = pre[i][u].second;
        ans += char('0' + d);
        u = pre[i][u].first;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";

    return 0;
}

总结

这个题的关键在于：

1. 将最大化平均值问题转化为二分 + 权值调整的判定问题。
2. 使用 AC 自动机快速计算所有咒语匹配的贡献。
3. 动态规划时记录前驱以输出方案。

这样就可以在 O(n * s * log(maxV)) 时间内解决。