0

如何找到以 M 为模的均匀分布的二项式系数的总和？
IE。( n C a + n C a+r + n C a+2r + n C a+3r + ... + n C a+kr ) % M = ?
给定：0 <= a < r, a + kr <= n < a + (k+1)r, n < 10 5 , r < 100

我的第一次尝试是：

int res = 0;
int mod=1000000009;
for (int k = 0; a + r*k <= n; k++) {
    res = (res + mod_nCr(n, a+r*k, mod)) % mod;
}

但这不是有效的。所以在阅读了这里 和这篇论文之后， 我发现上面的总和相当于：
summation[ω -ja * (1 + ω j ) n / r], for 0 <= j < r; ω = e i2π/r是一个原始的 r th单位根。
在 Order(r) 中找到这个总和的代码是什么？

编辑：n 可以达到 10 5并且 r 可以达到 100。

原始问题来源：https
://www.codechef.com/APRIL14/problems/ANUCBC比赛问题编辑：https
: //discuss.codechef.com/t/anucbc-editorial/5113 6年后重访此帖后来，我不记得我是如何将原始问题陈述转换为我的版本的，尽管如此，我还是分享了原始解决方案的链接，以防有人想看看正确的解决方法。

4

4 回答 4

2

二项式系数是多项式 (1+x)^n 的系数。x^a、x^(a+r)等的系数之和就是x^a在多项式环mod x^r-1中(1+x)^n的系数。多项式 mod x^r-1 可以由长度为 r 的系数数组指定。您可以通过重复平方计算 (1+x)^n mod (x^r-1, M) ，在每一步减少 mod x^r-1 和 mod M 。这需要大约 log_2(n)r^2 步和 O(r) 空间以及天真的乘法。如果您使用快速傅立叶变换对多项式进行乘法或取幂，则速度会更快。

例如，假设 n=20 和 r=5。

(1+x)    = {1,1,0,0,0}
(1+x)^2  = {1,2,1,0,0}
(1+x)^4  = {1,4,6,4,1}
(1+x)^8  = {1,8,28,56,70,56,28,8,1} 
           {1+56,8+28,28+8,56+1,70}
           {57,36,36,57,70}
(1+x)^16 = {3249,4104,5400,9090,13380,9144,8289,7980,4900}
           {3249+9144,4104+8289,5400+7980,9090+4900,13380}
           {12393,12393,13380,13990,13380}

(1+x)^20 = (1+x)^16 (1+x)^4
         = {12393,12393,13380,13990,13380}*{1,4,6,4,1}
           {12393,61965,137310,191440,211585,203373,149620,67510,13380}
           {215766,211585,204820,204820,211585}

这告诉您 a 的 5 个可能值的总和。例如，对于 a=1，211585 = 20c1+20c6+20c11+20c16 = 20+38760+167960+4845。

于 2015-04-04T02:04:00.003 回答
0

类似的东西，但你必须检查，a因为我只是放了任何东西而不考虑条件：nr

#include <complex>
#include <cmath>
#include <iostream>

using namespace std;

int main( void )
{
    const int r = 10;
    const int a = 2;
    const int n = 4;

    complex<double> i(0.,1.), res(0., 0.), w;

    for( int j(0); j<r; ++j )
    {
        w = exp( i * 2. * M_PI / (double)r );

        res += pow( w, -j * a ) * pow( 1. + pow( w, j ), n ) / (double)r;
    }

    return 0;

}
于 2014-04-10T22:32:29.083 回答
0

手术费用高mod，尽量避免

uint64_t res = 0;
int mod=1000000009;
for (int k = 0; a + r*k <= n; k++) {
    res += mod_nCr(n, a+r*k, mod);
    if(res > mod)
        res %= mod;
}

我没有测试这段代码

于 2014-04-13T12:12:04.783 回答
0

我不知道你是否在这个问题中达到了某些东西，但实现这个公式的关键是要真正弄清楚 w^i 是独立的，因此可以形成一个环。简单来说，您应该考虑实现 (1+x)^n%(x^r-1) 或在环 Z[x]/(x^r-1) 中找出 (1+x)^n 如果感到困惑我现在会给你一个简单的实现。

  1. 制作一个大小为 r 的向量。O(r) 空间 + O(r) 时间

  2. 在 O(r) 空间 +O(r) 时间处用零初始化这个向量

  3. 使该向量的前两个元素为 1 O(1)

  4. 使用快速求幂法计算 (x+1)^n。每个乘法需要 O(r^2) 并且有 log n 乘法因此 O(r^2 log(n) )

  5. 返回向量的第一个元素。O(1) 复杂度 O(r^2 log(n) ) 时间和 O(r) 空间。可以使用傅立叶变换将此 r^2 简化为 r log(r)。乘法是如何完成的，这是正则多项式乘法，幂为 mod

    向量 p1(r,0); 向量 p2(r,0); p1[0]=p1[1]=1；p2[0]=p2[1]=1；现在我们要做乘法向量 res(r,0); for(int i=0;i<r;i++) { for(int j=0;j<r;j++) { res[(i+j)%r]+=(p1[i]*p2[j] ); } } 返回水库 [0]; 我之前已经实现了这部分，如果您仍然对某些事情感到困惑，请告诉我。我希望您自己实现代码，但如果您需要代码，请告诉我。

于 2020-07-25T18:33:02.290 回答