将n作为k数之和写入的方式的数量，每个部分都有限制

Question

标题说明了一切。

我需要将n拆分为k部分的总和，其中每个部分ki应该在给定数组r的1 <= ki <= ri的范围内。

例如 -

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

订单很重要。 （2,1,1）和（1,2,1）是不同的。

我教过用星星和条形法解决它，但是因为上限ri我不知道接近它。

我实现了一个直接递归函数，它只适用于小值。

原始问题的制约因素是

1 <= n <= 107

1 <= k <= 105

1 <= ri <= 51

所有计算都将在Prime Modulo下完成。

我在这里发现了类似的问题，但我不知道如何在程序中实现。 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;
}

我没有使用地图来存储计算结果，而是使用了二维数组，它提供了非常好的性能提升，但由于n和k值很大，我无法使用它。

我怎样才能改进递归函数或解决这个问题的其他方法。

Answer 1

这是一个有趣的问题。

首先让我们说r_i = r_i - 1, n = n - k，[0, r_i]中的数字只是为了方便。现在可以添加一些虚构的数字，使m成为2的力量而不改变答案。

现在让我们将[0, r_i]的每个区间表示为多项式1 * x ^ 0 + 1 * x ^ 1 + ... + 1 * x & r_i。现在，如果我们将所有这些多项式相乘，那么x ^ n的系数将得到回答。

这里是称为数理论变换（NTT）的结构，它允许在p中乘以两个多项式模O(size * log(size))。

如果你只是使用NTT将它相乘，那么代码将在O(n * k * log (k * max(r)))中运行。这很慢。

但现在我们的虚拟数字有所帮助。让我们用分而治之的技巧。我们将制作O(log m)步骤，在每一步上乘以2 * i-th和2 * i + 1-th多项式。在下一步中，我们将乘以此步骤的结果多项式。

每一步都在O(k * log(k))工作，并且有O(log(k))步骤，所以algorhitm在O(k * log^2 (k))工作。它是渐近快速的，但我不确定它是否适合这个问题的TL。我认为它在最大测试时可以工作大约20秒。