计蒜客 腾讯的星钻增值服务

题意

计蒜客

做法

(m)种随机映射到(7)种,有(frac{7!}{7^7}approx 0.06)的可能得到正确结果

现在考虑(7)种,折半,分成((4,3)),然后暴力枚举
(2^7-2)去判断分组,使得暴力枚举的花费最小

结论:暴力枚举花费最小为(O(10^5))

令分好组后花费分别为(cnt_{min},cnt_{max}),最优则有(cnt_{min} imes Nge cnt_{max})(cnt_{min} imes cnt_{max}le (frac{n}{7})^7)
(cnt_{max}le sqrt{n imes (frac{n}{7})^7}approx 1.3 imes 10^5)

原文地址:https://www.cnblogs.com/Grice/p/12830479.html