理解Prime XOR的编辑-HackerRank

Question

免责声明：此问题涉及与相应编辑内容相关的内容。因此，如果您想自己尝试解决此问题，我不建议您阅读此帖子。此外，我的问题省略了编辑中提到的一些细节，请在阅读我的问题时参考编辑。请注意，我并不打算为HackerRank做广告; 此外，我不会以任何方式对编辑、问题描述或任何其他可能被HackerRank或其关联方视为侵犯版权的材料进行归属。

---

实际问题:

我试图理解问题的编辑部分。具体来说，我对以下代码片段感到困惑:

...
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 与该区间中奇数的数量相对应，但我不太明白它如何与一切联系起来。

感谢您的努力。

- Coder47

Answer 1

Flag的解释

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

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

换句话说，如果i为偶数，则将DP [i] [j]存储在mem [0] [j]中，如果i为奇数，则将其存储在mem [1] [j]中。 mem数组被多次重用，并且在每次迭代后保留完整DP数组的最近两行。

递归的解释

假设我们有5个值v的副本。 有1 + 5/2种方法可以使异或和为0（取0、2或4个副本）。有（1 + 5）/ 2种方法可以使异或和为v（取1、3或5个副本）。

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

- Peter de Rivaz

---

非常感谢您！ - Coder47

我尝试了两天使用哈希表来解决这个问题，而不是使用正常的数组，这应该会更快(因为所有的异或都集中在少量值上)。对于奇偶技巧，我使用了dp[i&1][xorval]和dp[(i+1)&1][xorval]，这是我最喜欢的技巧。 - KRoy

Answer 2

flag 用于减少内存的过度使用，因为 dp 只依赖于先前状态。

为什么循环 [0,8192]：由于问题中给出了 a[i]<=4500，所以当我们异或两个数字时，它将达到 8192。 异或属性..

- Atul Pandey