小编Cod*_*r47的帖子

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

另外,请记住,我不打算为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的平均数相对应,并且与同一时间间隔内的赔率数相对应,但我不知道它是如何与一切相关的.

在此先感谢您的努力.