蓝桥杯2023年第十四届省赛真题-异或和之和(递推)

解题思路:
异或和有一个性质，如果利用一个数组保存以A[i]结尾的异或和的每一个对应二进制位相加的和,那么求A[i+1]结尾的异或和的二进制位的和时，如果当前的二进制位是0，那么继承上一项位数，如果是1，则变为i减前一项的和加1。计算完毕后将二进制转化为数字。
注意事项:
复杂度O(logai*n)
参考代码:

#include<bits/stdc++.h>

#define maxx 110000

#define num 65

#define mod 998244353

#define int long long

using namespace std;

int n,m,actu;

int da,mxx,x,ls;

char c;

string s;

#define INF 0x3f3f3f3f

int er[num];

int all[maxx];

int dp[maxx][num];

int ans[maxx][num];

int ans1=0;

void e(int i)

{

    for(int j=1;j<=num;++j)

       {

          er[j]=i%2;

          i/=2;

       }                        

}signed main()

{

  scanf("%lld",&n);

  for(int i=1;i<=n;++i)

    scanf("%lld",&all[i]);

   for(int i=1;i<=n;++i)

    {

       e(all[i]);

       for(int j=1;j<=num;++j)

         ans[i][j]=er[j];

     }

    for(int i=2;i<=n;++i)

     for(int j=1;j<=num;++j)

      { if(ans[i][j]!=ans[i-1][j])

       ++dp[i][j];

        if(ans[i][j]==1)

      dp[i][j]+=(i-2-dp[i-1][j]);

      else

      dp[i][j]+=dp[i-1][j];

       }

    for(int i=1;i<=n;++i)

      for(int j=1;j<=num;++j)

         ans1+=dp[i][j]*(1<<(j-1));

    for(int i=1;i<=n;++i)

    ans1+=all[i];

    printf("%lld\n",ans1);

    /*for(int i=1;i<=n;++i)

     for(int j=1;j<=n;++j)

      {int v=0;

      for(int q=i;q<=j;++q)

       v=v^all[q];

       printf("%d %d %d\n",i,j,v);

      ans1+=v;}

        printf("%d",ans1);*/

}