了解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]可以存储可以用第一个元素形成的子集的数量,这样子集中元素的xor-sum是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阵列的最近两行.

再现的解释

假设我们有5个特定值的副本v.有1 + 5/2种方法使xor为0(取0,2或4个副本).有(1 + 5)/ 2种方法制作v的xor(取1,3或5副本).

因此,为了使新值j,我们可以从j开始并添加0或4个v的副本,或者从j ^ v开始并添加1,3或5个副本.