了解 Prime XOR 的社论 - HackerRank

Question

免责声明：本题涉及相应社论内容。因此，如果你想自己尝试这个问题，我不鼓励你阅读这篇文章 post。另外，我的问题遗漏了社论中提到的一些细节，所以请在阅读我的问题时参考社论。

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

实际问题：

我正在努力理解这篇 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;
}

社论指出“...使用这个属性，我们可以用 8192 常数因子编写一个 O(N) 动态编程解决方案，这样 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 个副本。

Answer 2

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

why loop [0,8192] ：正如问题中给出的那样 a[i]<=4500 然后当我们对两个数字进行异或时，它将达到 8192 。异或属性 ..

了解 Prime XOR 的社论 - HackerRank

Understanding the Editorial for Prime XOR - HackerRank

algorithm

boolean-logic

dynamic-programming

xor

标志说明

重复的解释