% mod formas compatíveis de gerar Coeficientes binomiais - c ++, algoritmo, coeficientes binomiais

Eu gostaria de otimizar uma parte do meu programa onde estou calculando a soma dos Coeficientes Binomiais até K. ou seja,

C(N,0) + C(N,1) + ... + C(N,K)

Desde que os valores vão além do tipo de dados (long long) pode suportar, eu sou para calcular valores mod M e estava procurando por procedimentos para fazer isso.

Atualmente, eu fiz isso com o Triângulo de Pascalmas parece estar tomando um pouco de carga. Então, eu estava me perguntando se há alguma outra maneira eficiente de fazer isso. Eu considerei o Teorema de Lucas, embora M eu já seja grande o suficiente para que C (N, k) fique fora de controle!

Quaisquer indicações de como eu posso fazer isso de forma diferente, talvez calcule toda a soma completamente com alguma outra expressão pura da soma. Se não, eu deixarei com o próprio método Triangle do Pascal.

Obrigado,

Aqui está o que eu tenho até agora O(N^2) :

#define MAX 1000000007
long long NChooseK_Sum(int N, int K){
vector<long long> prevV, V;
prevV.push_back(1);     prevV.push_back(1);
for(int i=2;i<=N;++i){
V.clear();
V.push_back(1);
for(int j=0;j<(i-1);++j){
long long val = prevV[j] + prevV[j+1];
if(val >= MAX)
val %= MAX;
V.push_back(val);
}
V.push_back(1);
prevV = V;
}
long long res=0;
for(int i=0;i<=K;++i){
res+=V[i];
if(res >= MAX)
res %= MAX;
}
return res;
}

Respostas:

Um algoritmo que executa um número linear de operações aritméticas bignum é

def binom(n):
nck = 1
for k in range(n + 1):  # 0..n
yield nck
nck = (nck * (n - k)) / (k + 1)

Isso usa divisão, mas modulo a prime p, você pode realizar praticamente a mesma coisa multiplicando pela solução i para a equação i * (k + 1) = 1 mod p. O valor que i pode ser encontrado em um número logarítmico de operações aritméticas via Algoritmo Euclidiano Estendido.