【题解】ABC 147 D Xor Sum 4

题目链接

下面的代码由于是比赛时写的不甚美观,如有疑问欢迎在下方评论区评论。

解题思路

其实这道题目想起来真的很简单很简单,但是特别容易取模的时候写挂。

这道题目的思路就是先将每一个数字转化成二进制,例如第二个样例:

0011
0001
0100
0001
0101
1001
0010
0110
0101
0011

然后用前缀和记录下每一个位的0和1的个数

个位:3个0,7个1
十位:6个0,4个1
百位:6个0,4个1
千位:9个0,1个1

然后从1到n枚举每一个数字,其中再从1-60枚举每一个位数。

找到这个数字之后与这一位相反的数字的个数即可。

然后就是我的智障时间

我把最后所有的算式集中成一个的时候(如下所示):

ans=ans%1000000007+(1<<(cnt-1)%1000000007*((all0[n-1][cnt]-all0[i][cnt])%1000000007))%1000000007;

他竟然挂了!!!

然后等到比赛结束2分钟,我把这个算式改成了

long long p=pow(2,cnt-1);
long long mul=p%1000000007;
long long cha=(all0[n-1][cnt]-all0[i][cnt])%1000000007;
long long anss=mul*cha%1000000007;
ans=ans%1000000007+anss;

于是本该加30几分的我掉了7分。。。

启示

这个蒟蒻的事例告诉我们千万不要把一堆式子压成一个式子,应该将每一步清清楚楚地写出来。

特别是取模的时候,很容易一下子就爆了原来的空间。

忘贴代码了

#include<bits/stdc++.h>
using namespace std;
long long a[300005];
long long all1[300005][65];
long long all0[300005][65];
int main(){
    long long n;
    cin>>n;
    long long cnt;
    for(long long i=0;i<n;i++){
        if(i!=0){
            for(long long j=0;j<65;j++){
                all1[i][j]=all1[i-1][j];
                all0[i][j]=all0[i-1][j];
            }
        }
        cnt=0;
        cin>>a[i];
        long long tmp=a[i];
        while(tmp!=0){
            cnt++;
            if(tmp%2==0){
                all0[i][cnt]++;
            }else if(tmp%2==1){
                all1[i][cnt]++;
            }
            tmp/=2;
        }
        for(long long j=cnt+1;j<65;j++){
            all0[i][j]++;
        }
    }
    long long ans=0;
    for(long long i=0;i<n;i++){
        long long tmp=a[i];
        cnt=0;
        while(tmp!=0){
            cnt++;
            long long p=pow(2,cnt-1);
            long long mul=p%1000000007;
            if(tmp%2==1){
                long long cha=(all0[n-1][cnt]-all0[i][cnt])%1000000007;
                long long anss=mul*cha%1000000007;
                ans=ans%1000000007+anss;
                ans=ans%1000000007;
            }else if(tmp%2==0){
                long long cha=(all1[n-1][cnt]-all1[i][cnt])%1000000007;
                long long anss=mul*cha%1000000007;
                ans=ans%1000000007+anss;
                ans%=1000000007;
            }
            tmp/=2;
        }
        for(int j=cnt+1;j<65;j++){
            long long p=pow(2,j-1);
            long long mul=p%1000000007;
            long long cha=(all1[n-1][j]-all1[i][j])%1000000007;
            long long anss=mul*cha%1000000007;
            ans=ans%1000000007+anss;
            ans=ans%1000000007;
        }
    }
    cout<<ans;
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/628/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者