algorithm - 将 n 写为 k 个数字之和的方法数，每个部分都有限制

Question

标题说明了一切。

我需要拆分n作为 k 的总和parts 其中每个部分 k_i 应该在范围内1 <= k_i <= r_i 对于给定数组 r .

例如-

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

订单很重要。 (2, 1, 1) 和 (1, 2, 1) 不同。

我教过用星条法解决它，但由于上限 r_i 我不知道如何接近它。

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

原始问题的约束是

1 <= n <= 10 7

1 <= k <= 10 5

1 <= r <子> i <= 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;
}

我没有使用映射来存储计算结果，而是使用了一个二维数组，它提供了非常好的性能提升，但我不能使用它，因为 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) 的结构，它允许在 O(size * log(size)) 中将两个多项式模 p 相乘。

如果您只是使用 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 秒。