algorithm - 了解 Prime XOR 的社论 - HackerRank

Question

免责声明:此问题涉及相应社论中的内容。因此，如果您想自己解决这个问题，我不鼓励您阅读这篇文章。另外，我的问题遗漏了社论中提到的一些细节，所以请在阅读我的问题时引用社论。

此外，请记住，我无意为 HackerRank 做广告；此外，我决不会将社论、问题描述或任何其他被 HackerRank 或关联方视为侵犯版权的 Material 的内容归功于自己。

---

实际问题:

我正在尝试理解这篇 problem 的社论.具体来说，我感到困惑的部分是以下代码:

...
for(int i=1;i<=k;i++) {
    for(int j=0;j<8192;j++) {
        mem[flag][j] = (mem[flag^1][j]*(1+(a[v[i-1]])/2))%mod + (mem[flag^1][j^v[i-1]]*((a[v[i-1]]+1)/2))%mod;
        if(mem[flag][j]>=mod)
            mem[flag][j]%=mod;
    }
    flag = flag^1;
}

社论指出“......使用这个属性，我们可以编写一个 O(N) 动态编程解决方案，其中 8192 常数因子使得 dp [i][j] 将存储可以由第一个元素组成的子集的计数，使得子集中元素的异或和为 j。”

从代码看来，mem 本质上是 dp，只是我无法理解 flag 的功能 - - 什么是 flag？另外，我得到 1 + (a[v[i - 1]])/2 对应于 [0, a[v[i - 1]]] 和 (a[v[i - 1]] + 1)/2对应于同一区间内的赔率数，但我看不出它与所有事物有何关系。

预先感谢您的努力。

Answer 1

标志说明

这是使用动态编程时减少内存使用的标准方法。

这个想法是，通常 DP 数组的每一行只依赖于前一行。在这种情况下，您可以只使用数组的 2 行，而不是存储整个 2d DP[i][j] 数组。

换句话说，如果 i 是偶数，DP[i][j] 存储在 mem[0][j] 中，如果 i 是奇数，则存储在 mem[1][j] 中。 mem 数组被多次重复使用，每次迭代后保存完整 DP 数组的最新两行。

复发的解释

假设某个值 v 有 5 个副本。有 1+5/2 种方法可以使 0 异或(取 0,2 或 4 个副本)。有 (1+5)/2 种方法可以对 v 进行异或运算(取 1,3 或 5 个副本)。

因此，要生成新值 j，我们可以从 j 开始并添加 v 的 0,2 或 4 个副本，或者从 j^v 开始并添加 1,3 或 5 个副本。