QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#633720#8520. Xor PartitionsTasbehWA 2ms5912kbC++172.1kb2024-10-12 16:07:002024-10-12 16:07:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 16:07:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5912kb
  • [2024-10-12 16:07:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long int ini;
ini mod=1e9+7;
ini a[300005][70];
ini b[300005][70];
ini solve(ini base,ini pow)
{
    if(pow==0) return 1;
    ini x=solve(base,pow/2)%mod;
    ini t=(((x%mod)*(x%mod))%mod*(base%mod))%mod;
    ini r=((x%mod)*(x%mod))%mod;
    if(pow%2) return t;
    else return r;
}
ini _do(ini x,ini y,ini tr[])
{
    bitset<70>g(x);
    bitset<70>f(y);
    ini sum=0;
    for(ini i=0;i<=68;i++)
    {
        if(f[i]!=g[i]) sum=(sum%mod+tr[i]%mod)%mod;
    }
    return sum;
}
int main()
{
    ini n;
    cin>>n;
    ini ar[n];
    for(ini i=0;i<n;i++) cin>>ar[i];
    ini tr[70]={0};
    tr[0]=1;
    for(ini i=1;i<=68;i++) tr[i]=((2%mod)*(tr[i-1]%mod))%mod;
    if(n==1) cout<<ar[0]<<endl;
    else if(n==2)
    {
        ini x=((ar[0]%mod)*(ar[1]%mod))%mod;
        ini y=_do(ar[0],ar[1],tr)%mod;
        cout<<(x%mod+y%mod)%mod<<endl;
    }
    else{
    ini br[n];
    br[1]=ar[0];
    br[0]=0;
    ini kr[n];
    kr[n-1]=ar[n-1];
    for(ini i=n-2;i>=0;i--) kr[i]=_do(kr[i+1],ar[i],tr)%mod;
    for(ini i=2;i<n;i++)
    {
        br[i]=_do(br[i-1],ar[i-1],tr)%mod;
    }

    bitset<70>bt(br[n-1]);


    for(ini i=0;i<=65;i++)
    {
        if(bt[i]==0) b[n-1][i]=ar[n-1]%mod,a[n-1][i]=0;
        else a[n-1][i]=ar[n-1]%mod,b[n-1][i]=0;
    }

    ini dum=0;
    for(int i=n-2;i>=0;i--)
    {
        ini sum=0;
        bitset<70>qt(br[i]);
        for(int j=0;j<=65;j++)
        {
            if(qt[j])
            {
                ini f=tr[j];
                sum=(sum%mod+((f%mod)*(b[i+1][j]%mod))%mod)%mod;
            }
            else{
                ini f=tr[j];
                sum=(sum%mod+((f%mod)*(a[i+1][j]%mod))%mod)%mod;
            }
        }


        sum=(sum%mod+kr[i]%mod)%mod;
        dum=sum;

        for(ini j=0;j<=65;j++)
        {
          if(qt[j]==0) b[i][j]=(b[i+1][j]%mod+sum%mod)%mod,a[i][j]=a[i+1][j];
          else a[i][j]=(a[i+1][j]%mod+sum%mod)%mod,b[i][j]=b[i+1][j];
        }

    }
    cout<<dum<<endl;
    }


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5600kb

input:

4
7 3 1 2

output:

170

result:

ok 1 number(s): "170"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5556kb

input:

3
1 2 3

output:

16

result:

ok 1 number(s): "16"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

4
0 1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 5912kb

input:

562
918479109239293921 960173570446350728 374394588863436385 418106819278123099 473761712658352147 662782574081105364 824954323015093862 827581845536521847 184394794881199801 820907621998888642 606529830885621237 961790689782125501 582742201855597942 337901250755571075 287706594894797714 18578215893...

output:

508621175

result:

wrong answer 1st numbers differ - expected: '641941658', found: '508621175'