草庐IT

c++ - 两个二项式系数的 GCD 模 10^9 + 7

coder 2024-02-24 原文

给定0 ≤ k ≤ n ≤ 500000，0 ≤ l ≤ m ≤ 500000。

我需要共同计算 GCD(C(n, k), C(m, l)) 模 10^9 + 7。

我的尝试:

我想到了 fourmula 的技巧: C(n, k) = n*(n-1)*...*(n-k+1)/k!

例如，假设 l >= k: GCD( C(n, k), C(m, l) ) = = GCD( n*(n-1)*...*(n-k+1)/k!, m*(m-1)*...*(m-l+1)/l! ) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l/l!, m*(m-1)*...* (m-l+1)/l!) = = GCD( n*(n-1)*...*(n-k+1)*(k + 1)*...*l, m*(m-1)*...*(m- l+1) )/l!

将 l! 的二进制求幂取反为 10^9 + 5 没问题，但我不知道如何继续。

这个 (k + 1)*...*l 部分毁了一切。如果乘数之间存在交集，我可以找到一些好处 n*(n-1)*...*(n-k+1) 和m*(m-1)*...*(m-l+1), 但如果不是，则整个 GCD 必须包含在此 (k + 1)*...*l 部分中。

然后呢？对剩余乘数使用 native GCD 算法？ 由于需要计算它们的乘积，又太长了，所以上面的操作看起来毫无意义。

我走的路对吗？ 有什么技巧可以解决这个问题吗？

最佳答案

根据 juvian 的建议，这非常简单。我怎么没有想到分解的想法!

我的 C++ 代码如下:

#include <iostream>
#include <algorithm>

#define NMAX 500000
#define MOD 1000000007

using namespace std;


long long factorial(long long n)
{
    long long ans = 1;
    for (int i = 2; i <= n; i++)
        ans = ans * i % MOD;
    return ans;
}

long long binPow(long long num, int p)
{
    if (p == 0)
        return 1;

    if (p % 2 == 1)
        return binPow(num, p - 1) * num % MOD;
    if (p % 2 == 0)
    {
        long long b = binPow(num, p / 2);
        return b * b % MOD;
    }
}

void primesFactorize(long long n, long long primes[])
{
    for (int d = 2; d * d <= n; d++)
        while(n % d == 0)
        {
            n /= d;
            primes[d]++;
        }
    if (n > 1) primes[n]++;
}

long long primes1[NMAX];
long long primes2[NMAX];

int main()
{
    long long n, k, m, l;

    cin >> k >> n >> l >> m;

    if (k > l)
    {
        swap(n, m);
        swap(k, l);
    }

    for (int i = n - k + 1; i <= n; i++)
        primesFactorize(i, primes1);

    for (int i = k + 1; i <= l; i++)
        primesFactorize(i, primes1);

    for (int i = m - l + 1; i <= m; i++)
        primesFactorize(i, primes2);

    for (int i = 2; i <= max(n, m); i++)
        primes1[i] = min(primes1[i], primes2[i]);

    long long ans = 1;
    for (int i = 2; i <= max(n, m); i++)
        for (int j = 1; j <= primes1[i]; j++)
            ans = ans * i % MOD;

    ans = ans * binPow(factorial(l), MOD - 2) % MOD;

    cout << ans << endl;
    return 0;
}

关于c++ - 两个二项式系数的 GCD 模 10^9 + 7，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51595642/

amp43longcodeprimesc++algorithmmathnumber-theorybinomial-coefficients

有关c++ - 两个二项式系数的 GCD 模 10^9 + 7的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  7. 由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2

    我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. ruby - ri 有空文件 – Ubuntu 11.10, Ruby 1.9 - 2

    我正在运行Ubuntu11.10并像这样安装Ruby1.9:$sudoapt-getinstallruby1.9rubygems一切都运行良好，但ri似乎有空文档。ri告诉我文档是空的，我必须安装它们。我执行此操作是因为我读到它会有所帮助:$rdoc--all--ri现在，当我尝试打开任何文档时:$riArrayNothingknownaboutArray我搜索的其他所有内容都是一样的。 最佳答案 这个呢？apt-getinstallri1.8编辑或者试试这个:(非rvm)geminstallrdocrdoc-datardoc-da

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐