Số cách viết n là tổng số k với các giới hạn trên mỗi phần

Question

Tiêu đề cho biết tất cả.

tôi cần phải chia n như tổng của k phần trong đó mỗi phần k _i phải ở trong phạm vi của = k _i < = r _i cho mảng cho r.

ví dụ -

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

thứ tự các vấn đề. (2, 1, 1) và (1, 2, 1) khác nhau.

Tôi đã dạy cách giải quyết nó bằng cách sử dụng phương pháp sao và thanh, nhưng là do giới hạn trên r _i tôi không biết cách tiếp cận nó.

tôi đã triển khai chức năng đệ quy trực tiếp và chỉ hoạt động tốt cho các giá trị nhỏ.

hạn chế của vấn đề gốc là

1 <= n <= 107

1 <= k <= 105

1 <= ri<= 51

Tất cả các phép tính sẽ được thực hiện dưới Modulo chính.

tôi đã tìm thấy sự cố tương tự ở đây nhưng tôi không biết cách triển khai trong chương trình. HERE

My brute-force đệ quy chức năng -

#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; 
} 

Thay vì sử dụng bản đồ để lưu trữ kết quả tính toán tôi được sử dụng một mảng hai chiều và nó đã cho tăng hiệu suất rất tốt, nhưng tôi không thể sử dụng nó vì lớn n và k giá trị.

Làm cách nào tôi có thể cải thiện chức năng đệ quy của mình hoặc cách khác để giải quyết vấn đề này.

Answer 1

Đó là vấn đề thú vị.

Đầu tiên cho phép nói r_i = r_i - 1, n = n - k, các số trong [0, r_i] chỉ để thuận tiện. Giờ đây, bạn có thể thêm một số con số hư cấu để tạo m sức mạnh của 2 mà không thay đổi câu trả lời.

Bây giờ, hãy đại diện cho mỗi khoảng thời gian [0, r_i] làm đa thức 1 * x^0 + 1 * x^1 + ... + 1 * x & r_i. Bây giờ nếu chúng ta nhân tất cả các đa thức, hệ số tại x^n sẽ là câu trả lời.

Đây là cấu trúc được gọi là Số chuyển đổi lý thuyết (NTT) cho phép nhân hai đa thức modulo p trong O(size * log(size)).

Nếu bạn chỉ cần nhân nó bằng NTT, mã sẽ hoạt động như sau: O(n * k * log (k * max(r))). Nó rất chậm.

Nhưng giờ đây số điện thoại hư cấu của chúng tôi giúp ích. Hãy sử dụng kỹ thuật phân chia và chinh phục. Chúng tôi sẽ thực hiện các bước O(log m), trên mỗi bước nhânvà 2 * i + 1 -th đa thức. Trong bước tiếp theo, chúng ta sẽ nhân các kết quả đa thức của bước này.

Mỗi bước hoạt động trong O(k * log(k)) và có O(log(k)) bước, vì vậy algorhitm hoạt động trong O(k * log^2 (k)). Đó là nhanh chóng tiệm cận, nhưng tôi không chắc chắn nếu nó phù hợp với TL cho vấn đề này. Tôi nghĩ rằng nó sẽ làm việc khoảng 20 giây trên thử nghiệm tối đa.