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

Question

标题说明了一切.

我需要分割n为k部分之和,其中每个部分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 _我我不知道接近它.

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

原始问题的制约因素是

1 <= n <= 107

1 <= k <= 105

1 <= ri <= 51

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

我在这里发现了类似的问题,但我不知道如何在程序中实现.这里

我的蛮力递归功能 -

#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。现在，如果我们将所有这些多项式相乘，则系数 atx ^ n将得到答案。

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

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