题意

你有一个长度为 $n$ 的模板串（由 $0-9$ 这 $10$ 个数字和通配符 $.$ 组成），还有 $m$ 个匹配串（只由 $0-9$ 这 $10$ 个数字组成），每个匹配串有一个魔力值 $v_i$。你要把模板串的每个 $.$ 都换成一个数字，使得模板串的魔力值最大。模板串的魔力值定义为：模板串中每出现一次任意一个匹配串 $s_i$，字符串的魔力就 $\times v_i$。最终魔力值开 $c$ 次方根，$c$ 为模板串中出现的匹配串的总数。

$1\le n,m,s\le 1501,\space 1\le v_i\le 10^9$

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

王·能过就行·子健

显然只要三个 $10^9$ 大小的数乘起来就爆 $long\space long$ 了（即 $\prod v_i$ 会很大），而高精度开根既难写又爆复杂度（光乘法就爆时间了），所以不能直接按题目的公式求。

如果你没学过数学（比如我），可以把所有 $v_i$ 各自开 $c$ 次方根再相乘，但即使开 $long\space double$ 也会爆精度，不过可以拿 $80$ 分。

如果你学过数学，应该记得高一数学必修 $1$ 中有一章讲了关于 $log$ 的各种性质，其中有两条是

$$log_a(MN) = log_a(M)+log_a(N)$$

$$log_a(N)^k = k\times log_a(N)$$

其中 $a$ 可以是任意底数。具体证明可以去翻书。

把两个公式组合一下，就可以推这题的公式

$$ans = \sqrt[c]{w_1\times w_2\times ...\times w_k} = (w_1\times w_2\times ...\times w_k)^{\frac{1}{c}}$$

两边同时取以一个实数 $a$ 为底的对数，得到

$$\log_a{ans} = \log_a{(w_1\times w_2\times ...\times w_k)^{\frac{1}{c}}}$$

$$\log_a{ans} = \frac{1}{c}\times \log_a{(w_1\times w_2\times ...\times w_k)}$$

$$\log_a{ans} = \frac{1}{c}(\log_a{w_1}+\log_a{w_2}+...+\log_a{w_k})$$

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄