题解 P3917 【异或序列】

hwk0518 · 2018-07-21 21:45:25 · 题解

我们定义第x个数中从右往左数第i位的贡献：有多少个在x之前的数j满足aj xor aj+1 xor ... xor ax的第i位是1.

设dp[x][i]表示第x个数第i位的贡献，a[x][i]表示第x个数第i位是多少。

若a[x][i]=0，取j=x不会产生贡献。若j小于x，aj xor aj+1 xor ... xor ax=aj xor aj+1 xor ... xor ax-1。所以dp[x][i]=dp[x-1][i].

若a[x][i]=1，取j=x产生1的贡献。若j小于x，aj xor aj+1 xor ... xor ax和aj xor aj+1 xor ... xor ax-1相反。所以dp[x][i]=(x-1-dp[x-1][i])(j小于x的贡献）+1(j=x的贡献）=x-dp[x-1][i].

设DP[x]=dp[x][0]×1+dp[x][1]×2+dp[x][2]×4+...+dp[x][31]×2^31.

则答案就是DP[1]+DP[2]+...+DP[n].

时间复杂度：O(32n)

空间复杂度：O(32n)

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

int n,a[100005],dp[100005][32];
long long ans;

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]);
    for(i=1;i<=n;++i)
        for(j=31;j>-1;--j)
        {
            if(a[i]&(1<<j)) dp[i][j]=i-dp[i-1][j];
            else dp[i][j]=dp[i-1][j];
            ans+=1LL*dp[i][j]*(1<<j);
        }
    printf("%lld",ans);
    return 0;
}

我们发现dp[x][i]的值只能由dp[x-1][i]转移得到，所以可以用滚动数组，边转移边统计答案。

时间复杂度：O(32n)

空间复杂度：O(32)

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

int n,a,dp[32];
long long ans;

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&a);
        for(j=31;j>-1;--j)
        {
            if(a&(1<<j)) dp[j]=i-dp[j];
            ans+=1LL*dp[j]*(1<<j);
        }
    }
    printf("%lld",ans);
    return 0;
}