algorithm - 了解 TPRODUCT 问题背后的数学算法

Question

我一直在尝试解决 codechef 问题:http://www.codechef.com/MAY11/problems/TPRODUCT/

他们在这里给出了赛后分析:http://www.codechef.com/wiki/may-2011-contest-problem-editorials

我需要一些帮助来理解那里讨论的逻辑:他们在谈论用对数代替函数

Pi=max(Vi*PL, Vi*PR)

数学不是我的强项。 [我一直在努力通过参加这样的比赛来提高]。如果有人能对这个问题给出一个非常愚蠢的解释，那对像我这样的凡人会有帮助。谢谢。

Answer 1

乘法的一个大问题是数字变得非常大非常快，并且存在达到 int 或 long 的上限并溢出到负数的问题。对数允许我们保持较小的计算量，然后以 n 为模得到答案。

在回溯通过动态规划找到的结果时，天真的解决方案是将所有值相乘，然后取模:

(x0 * x1 * x2 * ... * xk) (mod n)

这被一系列较小的计算所取代，从而避免了边界溢出:

z1 = e^(log(x0) + log(x1)) modulo n
z2 = e^(log(x2) + log(z1)) modulo n
...
zk = e^(log(xk) + log(z{k-1})) modulo n

然后 zk 包含结果。