# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
371207 | daniel920712 | Intergalactic ship (IZhO19_xorsum) | C++14 | 2088 ms | 44392 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
long long all[200005];
pair < pair < long long , long long > , long long > tt[200005];
vector < long long > how,how2,how3;
long long con[105]={0};
long long con2[105]={0};
long long ttt[100005][155]={0};
long long ttt2[100005][155]={0};
long long ttt3[100005][155]={0};
long long Pow[200005]={0};
long long ans=0,N,M,MOD=1e9+7;
int main()
{
long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
scanf("%lld",&N);
for(i=1;i<=N;i++) scanf("%lld",&all[i]);
scanf("%lld",&M);
Pow[0]=1;
for(i=0;i<M;i++) Pow[i+1]=Pow[i]*2%MOD;
for(i=0;i<M;i++) scanf("%lld %lld %lld",&tt[i].first.first,&tt[i].first.second,&tt[i].second);
for(i=1;i<=N;i++)
{
how.clear();
xx=0;
for(j=0;j<M;j++)
{
if(tt[j].first.first<=i&&tt[j].first.second>=i)
{
how.push_back(tt[j].second);
xx++;
}
}
for(j=0;j<128;j++) ttt[0][j]=0;
ttt[0][0]=1;
for(j=0;j<xx;j++)
{
for(k=0;k<128;k++) ttt[j+1][k]=ttt[j][k];
for(k=0;k<128;k++)
{
ttt[j+1][k^how[j]]+=ttt[j][k];
ttt[j+1][k^how[j]]%=MOD;
}
}
for(j=0;j<128;j++)
{
ans+=(all[i]^j)*(all[i]^j)%MOD*i%MOD*(N-i+1)%MOD*ttt[xx][j]%MOD*Pow[M-xx]%MOD;
ans%=MOD;
}
for(j=i+1;j<=N;j++)
{
how.clear();
how2.clear();
how3.clear();
xx=yy=zz=0;
for(k=0;k<M;k++)
{
if(tt[k].first.first<=i&&tt[k].first.second>=j)
{
how.push_back(tt[k].second);
xx++;
}
else if(tt[k].first.first<=i&&tt[k].first.second>=i)
{
how2.push_back(tt[k].second);
yy++;
}
else if(tt[k].first.first<=j&&tt[k].first.second>=j)
{
how3.push_back(tt[k].second);
zz++;
}
}
for(k=0;k<128;k++) ttt[0][k]=0;
ttt[0][0]=1;
for(k=0;k<xx;k++)
{
for(l=0;l<128;l++) ttt[k+1][l]=ttt[k][l];
for(l=0;l<128;l++)
{
ttt[k+1][l^how[k]]+=ttt[k][l];
ttt[k+1][l^how[k]]%=MOD;
}
}
for(k=0;k<128;k++) ttt2[0][k]=0;
ttt2[0][0]=1;
for(k=0;k<yy;k++)
{
for(l=0;l<128;l++) ttt2[k+1][l]=ttt2[k][l];
for(l=0;l<128;l++)
{
ttt2[k+1][l^how2[k]]+=ttt2[k][l];
ttt2[k+1][l^how2[k]]%=MOD;
}
}
for(k=0;k<128;k++) ttt3[0][k]=0;
ttt3[0][0]=1;
for(k=0;k<zz;k++)
{
for(l=0;l<128;l++) ttt3[k+1][l]=ttt3[k][l];
for(l=0;l<128;l++)
{
ttt3[k+1][l^how3[k]]+=ttt3[k][l];
ttt3[k+1][l^how3[k]]%=MOD;
}
}
for(m=0;m<128;m++)
{
a=0;
b=0;
for(k=0;k<128;k++)
{
a+=(all[i]^k^m)*ttt2[yy][k];
b+=(all[j]^k^m)*ttt3[zz][k];
a%=MOD;
b%=MOD;
}
ans+=2*a*b%MOD*ttt[xx][m]%MOD*Pow[M-xx-yy-zz]%MOD*i%MOD*(N-j+1)%MOD;
}
}
}
printf("%lld\n",ans);
return 0;
}
//936
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |