给出了两个整数n和k，都在100000范围内。
我们如何计算n* n-1 C 0（n 和 (n-1 选择 0) 的乘法）、n* n-1 C 1（n 和 (n-1 选择 1) 的乘法）、 n的 LCM * n-1 C 2 (n 和 (n-1 选择 2) 的乘法), .........., n* n-1 C k (n 和 (n-1 选择 k) 的乘法) ) 以1000000007为模。
我只是找到所有值，然后计算当数字增长时有很多问题的模数。
如何有效计算？
问问题
418 次
1 回答
3
一些想法：
很容易看出 lcm(nx, ny) = n*lcm(x, y) 所以实际上问题归结为计算 C 系数的 lcm。
也很容易看出 lcm(x/a, x/b) = x/gcd(a, b)，其中 gcd 是最大公约数。
如果你记得 n 选择 k = n!/k!(nk)! 这两个步骤将问题简化为计算
gcd(0!n!, 1!(n-1)!, 2!(n-2)!, ..., k!(nk)!)
然后除以 n*n! 由这个值。
gcd 可以通过欧几里得算法轻松计算。实际上还有更简单的方法：
gcd(i!(ni)!, (i+1)!(ni-1)!) = i!(ni-1)!gcd(ni, i+1)
（对于最后一个 gcd，您仍然必须使用欧几里得算法。但现在更容易了）。
您实际上可以在环模 1000000007 中进行所有计算。这意味着您可以在每次乘法/加法后取 1000000007 的余数，这不会影响答案。
最后你有两个值：
x = n*n！国防部 1000000007
y = gcd(0!n!, 1!(n-1)!, 2!(n-2)!, ..., k!(nk)!) mod 1000000007
您可以将 x 乘以 z，而不是除以这些数字，这样
z*y = 1 模 1000000007
您可以在本文中阅读更多关于此功能为何有效以及如何在此处找到此类 z 的信息。
- 您必须使用 64 位整数，因为即使是两个 1000000007 模数的乘积也不适合 32 位。或者，您可以编写自己的 mod-multiplication 算法，它不会溢出 32 位值（如果您知道如何编写乘法算法并在每一步后接受我关于计算 1000000007 余数的建议，这很容易做到）。
于 2015-10-07T15:15:27.093 回答