k個の数値の和としてnを書く方法の数。各部分に制限があります。

Question

タイトルはすべてです。各部K _Iが所与のアレイrため = K _I < = R _Iの範囲でなければならない場合

Iはk部品の合計としてnを分割する必要があります。例えば

-

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

注文事項。 （2,1,1）と（1,2,1）とは異なる。

私は星と棒の方法を使ってそれを解決することを教えましたが、上限のためにそうです。 _i私はそれに近づくことを知りません。

私は直接再帰関数を実装しましたが、小さな値に対してのみうまく動作します。元の問題の

制約

1 <= n <= 107

1 <= k <= 105

1 <= ri<= 51

あります

すべての計算は、モジュロの素数の下で行われます。

私は同様の問題を発見しましたが、私はプログラムでどのように実装するのか分かりません。 HERE

マイブルートフォース再帰関数 -

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

代わりの計算の結果を格納するためのマップを使用して、私は2次元配列を使用し、それは非常に良好なパフォーマンスの向上を与えたが、私は大きいためのそれを使用することはできませんnおよびk値。

どのように私の再帰関数を改善するか、この問題を解決する他の方法は何ですか？

Answer 1

これは興味深い問題です。

まずr_i = r_i - 1, n = n - kと言うと、便宜上、[0, r_i]の数字です。今や、答えを変更することなく2の力をmにするために架空の数字を追加することは可能です。

ここで、[0, r_i]の各区間を多項式1 * x^0 + 1 * x^1 + ... + 1 * x & r_iとして表現してみましょう。ここでこれらの多項式を掛け合わせると、係数はx^nになります。

O(size * log(size))に2つの多項式mododopを乗算することができるNumber Theoretic Transform（NTT）と呼ばれる構造があります。

NTTを使用して乗算すると、コードはO(n * k * log (k * max(r)))のようになります。それは非常に遅いです。

しかし、今私たちの架空の数字が役立ちます。分裂を利用して技術を征服しましょう。我々はO(log m)のステップを行い、各ステップで2 * i番目と2 * i + 1番目の多項式を掛けます。次のステップでは、このステップの結果の多項式を掛けます。

各ステップはO(k * log(k))で動作し、O(log(k))ステップがあるので、アルゴリズムはO(k * log^2 (k))で動作します。速く漸近的にですが、この問題にTLが適合するかどうかはわかりません。私はそれが最大のテストで約20秒動作すると思います。