c++ - 如何计算均匀分布的二项式系数之和

Question

如何找到以 M 为模的均匀分布的二项式系数之和？
IE。 (ⁿC_a + ⁿC_a+r + ⁿC_a+2r + ⁿC_a+3r + ... + ⁿC_{a+kr ) % M = ?
给定:0 <= a < r, a + kr <= n < a + (k+1)r, n < 10⁵, 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;
}

但是这样效率不高。所以看完here还有这个paper我发现上面的总和相当于:
求和[ω^-ja * (1 + ω^j)ⁿ/r], 对于 0 <= j < r; ω = e^i2π/r 是原始单位根 r^th。
在 Order(r) 中找到这个总和的代码是什么？

编辑:n 可以达到 10⁵，r 可以达到 100。

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

Answer 1

二项式系数是多项式 (1+x)^n 的系数。 x^a、x^(a+r)等的系数之和就是多项式环mod x^r-1中(1+x)^n中x^a的系数。多项式 mod x^r-1 可以由长度为 r 的系数数组指定。您可以通过 repeated squaring 计算 (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。