牛客小白月赛11 Rinne Loves Xor

题目链接：https://ac.nowcoder.com/acm/contest/370/I
code:
#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

ll mod=1e9+7;

ll pow(ll x,ll n,ll mod)

{

    ll res=1;

	while(n>0)

	{

	   if(n%2==1)

	   {

	   	 res=res*x;

	   	 res=res%mod;

	   }

	   x=x*x;

	   x=x%mod;

	   n>>=1;

	}

	return res;

}

int n;

ll a[100005];ll b[100005];ll c[100005];

ll suma[35];

ll sumb[35];

void cal(int i)

{

    ll num=a[i];

    for(int j=0;j<35;j++)

        if(num>>j&1)suma[j]++;

    num=b[i];

    for(int j=0;j<35;j++)

        if(num>>j&1)sumb[j]++;

}

ll f(int i)

{

    ll res=0;ll nowa=a[i];

    for(int j=0;j<35;j++)

    {

        if(nowa>>j&1)

        {

            res=(res+1ll*(i-sumb[j]-1)*pow(2,j,mod)%mod)%mod;

        }

        else

        {

            res=(res+1ll*sumb[j]*pow(2,j,mod)%mod)%mod;

        }

    }

    ll nowb=b[i];

    for(int j=0;j<35;j++)

    {

        if(nowb>>j&1)

        {

            res=(res+1ll*(i-suma[j]-1)*pow(2,j,mod)%mod)%mod;

        }

        else

        {

            res=(res+1ll*suma[j]*pow(2,j,mod)%mod)%mod;

        }

    }

    cal(i);

    return res;

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);

    ll tmp=0;

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

    {

        tmp=(tmp+(a[i]^b[i]))%mod;

        tmp=(tmp+f(i))%mod;

        c[i]=tmp;

    }

    for(int i=1;i<=n;i++)printf("%lld%c",c[i],i==n?'\n':' ');

    return 0;

}
巴特西

牛客小白月赛11 Rinne Loves Xor

最新文章

热门文章
