Как вычислить сумму равномерно распределенных биномиальных коэффициентов
Как найти сумму равномерно распределенных биномиальных коэффициентов по модулю M?
то есть. (NС + NСа + г + NСа + 2г + NСа + 3r + … + NСа + кр)% M =?
дано: 0 <= а < г, а + кр <= n < a + (k + 1) r, n < 105, р < 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;
}
но это не эффективно. Итак, после прочтения Вот
и это бумага Я узнал, что вышеуказанная сумма эквивалентна:
Суммирование [ω-JA * (1 + ωJ)N / г], для 0 <= j < р; и ω = еi2π / г это примитивный гго корень единства.
Какой может быть код для поиска этой суммы в Order (r)?
Редактировать:
N может подняться до 105 и г может подняться до 100.
Решение
Биномиальные коэффициенты — это коэффициенты полинома (1 + x) ^ n. Сумма коэффициентов x ^ a, x ^ (a + r) и т. Д. Является коэффициентом x ^ a в (1 + x) ^ n в кольце многочленов mod x ^ r-1. Полиномы mod x ^ r-1 могут быть заданы массивом коэффициентов длины r. Вы можете вычислить (1 + x) ^ n мод (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}
Это говорит вам суммы для 5 возможных значений a. Например, для a = 1 211585 = 20c1 + 20c6 + 20c11 + 20c16 = 20 + 38760 + 167960 + 4845.
Другие решения
Нечто подобное, но вы должны проверить a, n а также r потому что я просто что-то положил, не задумываясь о состоянии:
#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;
}
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;
}
Я не тестировал этот код