Я хотел бы оптимизировать часть моей программы, где я вычисляю сумму биномиальных коэффициентов до К. Т.е.

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

Так как значения выходят за рамки типа данных (long long), которые можно поддерживать, я рассчитываю значения модM и искал процедуры для этого.

В настоящее время я сделал это с помощью треугольника Паскаля, но, похоже, он немного загружен. поэтому мне было интересно, есть ли другой эффективный способ сделать это. Я рассмотрел теорему Лукаса, хотя M у меня уже достаточно велико, так что C (N, k) выходит из-под контроля!

Любые указатели на то, как я могу сделать это по-другому, возможно, рассчитать всю сумму вместе с некоторым другим аккуратным выражением суммы. Если нет, я оставлю это с помощью самого метода треугольника Паскаля.

Спасибо,

Вот что у меня так далеко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;
}