Liczba sposobów zapisywania n jako suma liczb k z ograniczeniami dla każdej części

Question

Tytuł mówi wszystko.

trzeba podzielić n jako suma k części, w których każda z części K _i powinna być w zakresie od = k _i < = R _i dla danej tablicy r.

na przykład -

n = 4, k = 3 and r = [2, 2, 1] 
ans = 2 
#[2, 1, 1], [1, 2, 1] 

sprawy kolejności. (2, 1, 1) i (1, 2, 1) są różne.

Nauczyłem go rozwiązywać, stosując metodę gwiazd i pasków, ale z powodu górnej granicy r _i Nie wiem, aby do niego podejść.

Zaimplementowałem funkcję bezpośredniej rekursji i działa ona dobrze tylko dla małych wartości.

Ograniczenia pierwotnego problemu są

1 <= n <= 107

1 <= k <= 105

1 <= ri<= 51

Wszystkie obliczenia zostaną wykonane pod głównym modulo.

Znalazłem podobny problem tutaj, ale nie wiem, jak zaimplementować w programie. HERE

My brute-force rekurencyjna funkcja -

#define MAX 1000 
const int md = 1e9 + 7; 

vector <int> k; 
vector <map<int, int>> mapper; 

vector <int> hold; 

int solve(int sum, int cur){ 

    if(cur == (k.size() - 1) && sum >= 1 && sum <= k[cur]) return 1; 
    if(cur == (k.size() - 1) && (sum < 1 || sum > k[cur])) return 0; 

    if(mapper[cur].find(sum) != mapper[cur].end()) 
     return mapper[cur][sum]; 

    int ans = 0; 
    int start = 1; 

    for(int i=start; i<=k[cur]; ++i){ 


     int remain = sum - i; 
     int seg = (k.size() - cur) - 1; 
     if(remain < seg) break; 

     int res = solve(sum - i, cur + 1); 
     ans = (1LL * ans + res) % md; 
    } 

    mapper[cur][sum] = ans; 
    return ans; 
} 


int main(){ 

    for(int i=0; i<MAX; ++i) k.push_back(51); // restriction for each part default 51 
    mapper.resize(MAX); 

    cout << solve(MAX + MAX, 0) << endl; 
} 

Zamiast pomocą mapy do przechowywania wyników obliczeń użyłem dwuwymiarową tablicę i dała bardzo dobry wzrost wydajności, ale nie można go używać ze względu na duże wartości n i k.

Jak mogę poprawić swoją funkcję rekurencyjną lub jakie są inne sposoby rozwiązania tego problemu.

Answer 1

To interesujący problem.

Najpierw powiedzmy r_i = r_i - 1, n = n - k, numery w [0, r_i] tylko dla wygody. Teraz można dodać kilka fikcyjnych liczb, aby uzyskać m moc 2 bez zmiany odpowiedzi.

Teraz przedstawiamy każdy przedział [0, r_i] jako wielomian 1 * x^0 + 1 * x^1 + ... + 1 * x & r_i. Teraz, jeśli pomnożymy wszystkie te wielomiany, będzie to współczynnik o numerze x^n.

Oto struktura o nazwie Numeryczna Transformacja Teoretyczna (NTT), która umożliwia pomnożenie dwóch wielomianów modulo p w O(size * log(size)).

Jeśli po prostu pomnożysz go za pomocą NTT, kod zadziała w sposób podobny do O(n * k * log (k * max(r))). Jest bardzo powolny.

Ale teraz pomagają nam nasze fikcyjne liczby. Wykorzystajmy technikę dziel i rządźmy. Zrobimy O(log m) kroków, na każdym kroku pomnóżmy 2 * i -th i -th wielomian. W następnym kroku pomnożymy wynikowe wielomiany tego kroku.

Każdy krok działa w O(k * log(k)) i jest O(log(k)) kroków, więc algorhitm działa w O(k * log^2 (k)). Jest szybki asymptotycznie, ale nie jestem pewien, czy pasuje on do tego problemu. Myślę, że będzie działać około 20 sekund na maksymalnym teście.