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

题意

计蒜客

做法

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

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

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

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

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

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