使用模数是否有利于高数字？

Question

将在0-32范围内添加6个随机唯一数字并对结果进行模数有利于高数字？

示例:9 +10 +11 +18 +25 +28 +32 = 133%20 = 13

Answer 1

有趣的是,有一种强大的方法可以用来手动计算,或者使用生成函数的概念在计算机上非常快(而不是使用蛮力).

(警告:长篇文章)

您正在0到19的范围内工作,但是通过从0-32随机生成数字来实现.

如果得到数字i的机会是p(i)[注,p(0)= p(1)= p(2)= ... = p(12)和p(13)= .. = p( 19)和p(0)= 2p(13)).

现在我们感兴趣的是通过生成6次随机数并将它们相加来获得特定总和的机会.

这可以通过计算多项式的六次幂中的系数来建模

P(x)= p(0)+ p(1)*x + p(2)*x ^ 2 + ... + p(r)*x ^ r + ... + p(19)*x ^ 19

因此,我们正在研究(P(x))^ 6的系数.

对于给定的问题,我们可以忽略1/33因子(为了比较哪个和更有可能)并且p(0)= 2,p(1)= 2,...,p(19)= 1 .

因此,我们看P(x)= 2(1 + x + x ^ 2 + ... + x ^ 12)+ x ^ 13 + x ^ 14 + .. + x ^ 19.

我们现在只需要计算其第六次幂的系数,将指数模数为20并将它们相加.这里可以使用像FFT这样的快速多项式乘法算法.

实际上,我们可以使用一些具有复数的代数手动完成它和/或证明有关定罪的概率分布的陈述.