「BJOI2019」奥术神杖(AC自动机+DP)

文章目录

title

solution

令 M a g i c = V i × V j × V k . . . Magic=V_i\times V_j\times V_k... Magic=Vi​×Vj​×Vk​...
这里对 M a g i c c \sqrt[c]{Magic} cMagic ​有一个很巧妙的转换——取对数
M a g i c c = ( M a g i c ) 1 c = e l o g e ( M a g i c ) 1 c \sqrt[c]{Magic}=(Magic)^{\frac{1}{c}}=e^{log_e(Magic)^{\frac{1}{c}}} cMagic ​=(Magic)c1​=eloge​(Magic)c1​ l o g e   M a g i c 1 c = 1 c l o g e   M a g i c = 1 c l o g e ( V i × V j × V k . . . ) log_e\ Magic^{\frac{1}{c}}=\frac{1}{c}log_e\ Magic=\frac{1}{c}log_e(V_i\times V_j\times V_k...) loge​ Magicc1​=c1​loge​ Magic=c1​loge​(Vi​×Vj​×Vk​...) = 1 c × ( l o g e V i + l o g e V j + l o g e V k . . . ) =\frac{1}{c}\times (log_eV_i+log_eV_j+log_eV_k...) =c1​×(loge​Vi​+loge​Vj​+loge​Vk​...)
于是就成功把神力值的相乘开方变为了相加
( l o g e V i + l o g e V j + l o g e V k . . . c ) m a x (\frac{log_eV_i+log_eV_j+log_eV_k...}{c})_{max} (cloge​Vi​+loge​Vj​+loge​Vk​...​)max​

上一篇:python 格式化字符串"%s"%


下一篇:「BJOI2019」奥术神杖