Submission #371207

#TimeUsernameProblemLanguageResultExecution timeMemory
371207daniel920712Intergalactic ship (IZhO19_xorsum)C++14
47 / 100
2088 ms44392 KiB
#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)

xorsum.cpp: In function 'int main()':
xorsum.cpp:21:25: warning: unused variable 'x' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                         ^
xorsum.cpp:21:29: warning: unused variable 'y' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                             ^
xorsum.cpp:21:33: warning: unused variable 'z' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                 ^
xorsum.cpp:21:37: warning: unused variable 'ok' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                     ^~
xorsum.cpp:21:42: warning: unused variable 'ans2' [-Wunused-variable]
   21 |     long long i,j,k,l,m,x=1,y=1,z=1,ok=1,ans2=0,xx=0,yy,zz,a,b;
      |                                          ^~~~
xorsum.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:23:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     for(i=1;i<=N;i++) scanf("%lld",&all[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~
xorsum.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%lld",&M);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     for(i=0;i<M;i++) scanf("%lld %lld %lld",&tt[i].first.first,&tt[i].first.second,&tt[i].second);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...