题意

给定一个长为 nn 的字符串 SS，其每一位为数字 0∼90\sim 9 或一个 .. 字符，后者表示该位可以为任何数字。
再给定 mm 个字符串 TiT_i，每个字符串有其对应的权值 ViV_i。
初始时有变量 Magic=1\mathcal{Magic} = 1 和 Count=0\mathcal{Count} = 0。
每当 TiT_i 在 SS 中出现一次（即不同位置出现算作多次），我们就将 Magic\mathcal{Magic} 乘上 ViV_i，并将 Count\mathcal{Count} 加上 11。
最终的答案为 Answer=MagicCount\mathcal{Answer} = \sqrt[\mathcal{Count}]{\mathcal{Magic}}。
要求找到一种填充字符串内 .. 字符的方案，使得 Answer\mathcal{Answer} 最大，并且需要输出一种满足其的填充字符串的方案。
Data Range:1≤n,m≤1501,1≤Vi≤109,1≤∑i=1m∣Ti∣≤1501\mathcal{Data~Range}: 1 \le n, m \le 1501, 1 \le V_i \le 10^9, 1 \le \displaystyle{\sum_{i = 1}^m} |T_i| \le 1501

题解

（你真的会高精度开任意次方根吗？）

所以这题显然要在答案的式子上下点功夫。

和乘积有关的题目，一个好的思路是化乘为加。我们如果把每个 ViV_i 都求 ln⁡\ln，就可以把 Magic\mathcal{Magic} 由求积转化为求和了，并且这样的转化并不会影响答案之间的大小关系。

而 Count\mathcal{Count} 次方根这个部分，可以发现它直接变成了 1Count\displaystyle \frac{1}{\mathcal{Count}}，所以原式就化为了 MagicCount\displaystyle \frac{\mathcal{Magic}}{\mathcal{Count}}。

我们再重新审视一遍 Magic\mathcal{Magic} 和 Count\mathcal{Count}：每次当前者加上一个 ViV_i 时，后者就会加上一个 11，而又因为两者的贡献是呈分数形式的，所以我们需要用到的算法已经很明显了 —— 分数规划。

考虑分数规划的经典解法，我们二分一个答案 midmid，那么有：

∑i=1CountViCount>mid∑i=1CountVi>Count∗mid∑i=1Count(Vi−mid)>0\begin{matrix} \dfrac{\displaystyle{\sum_{i = 1}^{\mathcal{Count}} V_i}}{\mathcal{Count}} > mid \\ \displaystyle{\sum_{i = 1}^{\mathcal{Count}}} V_i > {\mathcal{Count}} * mid \\ \displaystyle{\sum_{i = 1}^{\mathcal{Count}}} (V_i - mid) > 0 \end{matrix}

推导到这里，可以发现，只要给每一个权值减去一个 midmid，那么这个式子的值和 Count\mathcal{Count} 的具体值已经没有任何关系了。

剩下的部分，就是求出左侧式子的最大值，然后和 00 比较了。

而我们要如何求这个最大值呢？可以发现它和普通的分数规划不太一样：我们无法决定每个贡献的系数是 00 还是 11。

我们再次重新审视一遍这个问题：填充 SS 的所有 .. 字符，使得出现的所有 TiT_i 的权值和最大。

对于这种涉及到了字符串的多模匹配的问题，我们可以考虑用 AC⁡\operatorname{AC} 自动机来解决。具体地，设 fi,jf_{i, j} 表示走到自动机的 ii 号节点，同时 SS 串已经填完了前 jj 个字符，在这种情况之下我们能够得到的最大权值。

转移很简单，由于自动机具有优美的结构，因此我们仅需每次枚举下一个字符进行转移即可。注意由于我们最终需要输出一个满足要求的字符串，因此转移时需要记录前驱状态和转移时枚举的字符。

最后一个问题来了：如何处理自动机上每个点的贡献？

显然，对于一个点，如果它对应了一个 TiT_i，那么在 Fail\mathcal{Fail} 树中以它为根的子树都需要加上它的权值。所以，对于每一个 midmid，我们利用树上差分重构一遍自动机上每个点的贡献即可。

代码实现

完