QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#712127 | #8520. Xor Partitions | ucup-team4992# | AC ✓ | 194ms | 8068kb | C++20 | 1.3kb | 2024-11-05 14:38:58 | 2024-11-05 14:38:58 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5,mod=1e9+7,M=60;
int num[65],pos,n;
ll A[N];
ll sum[65][2];
ll dp[N],fpow[65];
void init(){
fpow[0]=1;
for(int i=1; i<=M; i++) fpow[i]=fpow[i-1]<<1,fpow[i]%=mod;
}
void calc(ll x){
pos=0;
while(x){
num[pos++]=x&1;
x>>=1;
}
for(; pos<=M; pos++) num[pos]=0;
}
void solve(){
cin>>n;
for(int i=0; i<=60; i++) sum[i][1]=1;
for(int i=1; i<=n; i++){
ll x;
cin>>x;
calc(x);
for(int j=0; j<=M; j++){
dp[i]+=sum[j][num[j]]*fpow[j]%mod; dp[i]%=mod;
// cout<<"num["<<j<<"] = "<<num[j]<<" , sum["<<j<<"] = "<<sum[j][0]<<" , "<<sum[j][1]<<"\n";
}
// cout<<"dp["<<i<<"] = "<<dp[i]<<"\n";
for(int j=0; j<=M; j++){
if(num[j]) swap(sum[j][0],sum[j][1]);
sum[j][1]+=dp[i]; sum[j][1]%=mod;
// cout<<"num["<<j<<"] = "<<num[j]<<" , sum["<<j<<"] = "<<sum[j][0]<<" , "<<sum[j][1]<<"\n";
}
// cout<<"\n";
}
cout<<dp[n]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
init();
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5732kb
input:
4 7 3 1 2
output:
170
result:
ok 1 number(s): "170"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
1 0
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
3 1 2 3
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
4 0 1 0 1
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
562 918479109239293921 960173570446350728 374394588863436385 418106819278123099 473761712658352147 662782574081105364 824954323015093862 827581845536521847 184394794881199801 820907621998888642 606529830885621237 961790689782125501 582742201855597942 337901250755571075 287706594894797714 18578215893...
output:
641941658
result:
ok 1 number(s): "641941658"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
806 154088894908249861 515620644168920420 987371724389985655 237699073224022026 870013393084040616 381176515155022022 684658378726319957 263518193038353112 315710296046387135 551218921219797967 118207002034108547 368754899860827737 935813803983235940 144555339393414539 776366257845243712 97482835862...
output:
322263213
result:
ok 1 number(s): "322263213"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5608kb
input:
730 504625950218841699 11051067425914472 76969373706503912 549617734382960079 841136352271894226 827409290048280121 385214931443507037 450322494678858761 648956361691910260 885215198848035026 943077096807914988 563680977442136779 928183411196746637 238397217357311158 42194234771144128 13855813780489...
output:
302666182
result:
ok 1 number(s): "302666182"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
810 799481157885297669 36700891760566107 106799307598176179 525457060642356612 692305388685262192 734925968562669769 944342162656870872 318551639297444833 948338452318307252 947010621108694579 847591264136215873 843729821439293876 795197982657816209 514358412232554388 824474357024876223 262652125198...
output:
602149347
result:
ok 1 number(s): "602149347"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
753 19680670121054815 730848550760427515 382393175530043476 135251628628086143 953972980324431759 968402030274542386 239081692291889007 208406098506299898 210617837980094596 241386761622363415 614349192152783697 674634709373373543 954789607048365380 176448580882244695 495604367525148905 838787911842...
output:
444552931
result:
ok 1 number(s): "444552931"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
1000 5910966043171798 444610656319788280 3688812861187777 527406121506858974 348651678231967453 742595325576725873 269979149588588141 367500509520651713 721087042810251324 781730710329969382 273470825025201702 217943660725681870 798497786765762465 932985478420399210 51222819072897891 123000680900329...
output:
375397549
result:
ok 1 number(s): "375397549"
Test #12:
score: 0
Accepted
time: 7ms
memory: 5764kb
input:
10000 836416588552416746 715139925233188073 540045750150764470 657083656580111699 453024602030341020 32332432208735263 675754504084029016 182620749259887560 238151424129511167 51110718389056302 51405438498364014 122526276542156527 610483897196537731 847874891186284312 145487013148799803 786588991661...
output:
465337540
result:
ok 1 number(s): "465337540"
Test #13:
score: 0
Accepted
time: 62ms
memory: 6472kb
input:
100000 730682239762265959 307059402620664122 115979858233261975 244728110596258449 879226800697788913 227027291248976655 132171973066857319 837530086673521636 990238586667417326 344010698420539749 52603681260480846 974344540159711285 136286036328847931 585214727445181288 444702707623149922 204441001...
output:
837391091
result:
ok 1 number(s): "837391091"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
122 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 193ms
memory: 7876kb
input:
290961 846377657091027963 867642083997864998 318092818587796046 622637207479893557 96527938269242434 765910401421070700 111007328062052438 784134329098500458 809741882237463364 184802786004174581 848102178687474272 396434268861505821 51257684464611016 536944824906958774 713116046434570909 6816680330...
output:
940131269
result:
ok 1 number(s): "940131269"
Test #16:
score: 0
Accepted
time: 190ms
memory: 7948kb
input:
299681 462697757809264437 389048631084523318 51749456665227841 96779403227006809 769124977734026840 508360511619681262 908679820421609812 196303563263661979 319573370437790571 498142848986298809 504387423759523001 181030641077997424 276642772662399333 93671130729361755 988639804042989696 55261120349...
output:
621006152
result:
ok 1 number(s): "621006152"
Test #17:
score: 0
Accepted
time: 191ms
memory: 7836kb
input:
294249 732447652922382719 270020677717613853 863766069735717014 24550222610980340 750958924999754557 834452767844492364 819443732411875432 393171106666384024 392109387690742935 29909919449555927 891727531898858023 32983177861558029 760641765483789811 8965640318318128 736535536536189201 8754309146083...
output:
714968459
result:
ok 1 number(s): "714968459"
Test #18:
score: 0
Accepted
time: 190ms
memory: 7536kb
input:
299135 385544154768009445 549747363305315818 690291944234898801 14601156984063223 278983871639397249 399974862472298146 900241264258377346 586674980374007242 176631173083309189 319465591867786045 282061730513897788 448223245115828316 521758577957274274 61097192697492613 3173770253171900 815477652164...
output:
492094653
result:
ok 1 number(s): "492094653"
Test #19:
score: 0
Accepted
time: 187ms
memory: 7992kb
input:
294404 98400934769999698 404774893094823438 883283529713143566 129527983585008088 627318323268441796 49824532466539484 310650525998415217 834865996068574349 945946050904038172 581860660854189208 154375985088718476 765554777144309745 118785359051433488 323613201270591227 166378816589630113 3688813506...
output:
607655770
result:
ok 1 number(s): "607655770"
Test #20:
score: 0
Accepted
time: 194ms
memory: 7984kb
input:
299996 414420137641408190 762336580318865458 452038972285052843 693265038374061112 596620074582746351 36863084346310498 641476186504216790 53161695347445918 86278085401843807 443738644720471766 184576791013806403 674115173798296425 65990997694497708 189763148973413990 279070372440294215 876432291484...
output:
412741065
result:
ok 1 number(s): "412741065"
Test #21:
score: 0
Accepted
time: 190ms
memory: 8012kb
input:
299997 577429729307964715 278357628994142161 146381786336988996 781905154454976316 820460442136759827 21721154147288267 353947755616445551 773376008016269011 631655715059833382 981403648314053998 282279562015598473 298175609893887249 827594724727316042 976222537485393459 400150062525076017 841678353...
output:
135504307
result:
ok 1 number(s): "135504307"
Test #22:
score: 0
Accepted
time: 194ms
memory: 7948kb
input:
299998 862693192076980995 137119090578215886 371635959707377560 390544363233672515 141015436689850278 705873619623409361 742594640341831408 368066310356938990 196398995629239730 219617014791422754 414284162738028565 278361775192400906 243813232100950898 787864496602348976 575976078767114916 55770462...
output:
577245228
result:
ok 1 number(s): "577245228"
Test #23:
score: 0
Accepted
time: 182ms
memory: 8008kb
input:
299999 407632102033853375 250729121712464021 736608436606343166 474685213834128786 346515740642504286 227090587850987335 817171803949652843 449864853844145176 799510495874918662 714183748892334582 514006609614771461 234917591978692526 939629567273793814 71036632547860292 152513112283707297 752952439...
output:
588852000
result:
ok 1 number(s): "588852000"
Test #24:
score: 0
Accepted
time: 190ms
memory: 7612kb
input:
300000 876653344583117344 599625758589217969 375091999928856826 276809429671397145 406175686443747945 528479375858125124 470749448734264181 769944314510776935 481776876276331801 737387902312433065 485066084973509663 225081457594113207 564895091868198061 128952864484076012 445508889974365735 22711969...
output:
571048948
result:
ok 1 number(s): "571048948"
Test #25:
score: 0
Accepted
time: 189ms
memory: 8020kb
input:
299194 38220865220722874 833513435383712608 147475262218163940 809155071467993253 151093099481639268 8842576275361023 147899768560405316 509818676839100474 108200410409094395 840440989281919442 128263954681043190 46470778696868556 339098188382400808 774919173492221022 483486485963389 973490418403891...
output:
796320682
result:
ok 1 number(s): "796320682"
Test #26:
score: 0
Accepted
time: 187ms
memory: 8028kb
input:
290852 776347822513774533 201166095630909711 579991579184209610 190368086959642985 582066502881054536 772293268110693921 132457693910552947 890383977796261561 761245640042890380 512753819673871174 4299163648 293296182395574799 434734209271056818 323364135697422379 274996170754068224 3655481957371152...
output:
540200763
result:
ok 1 number(s): "540200763"
Test #27:
score: 0
Accepted
time: 186ms
memory: 8068kb
input:
295315 178802475354908523 178800276331652971 228503023277267100 359929001024844693 339488891850894036 274323955954480564 883809678695165694 224592536614421135 499059874648314634 684256272482175762 310634414033465289 95362682032715931 255896077813095006 640946955797570689 743631191715753704 956355515...
output:
778174413
result:
ok 1 number(s): "778174413"
Test #28:
score: 0
Accepted
time: 182ms
memory: 8000kb
input:
295102 289841334191992832 848992159784645487 753259529803322988 46100801341965631 815961364919735690 686172697373924066 284573267737719771 858534451031507339 750686373049794731 595080834313779112 151495590628989383 81320591287596192 168756217368714203 922209450386260712 840528518704984631 5365942201...
output:
148286240
result:
ok 1 number(s): "148286240"
Test #29:
score: 0
Accepted
time: 192ms
memory: 8000kb
input:
298827 523530202042597193 140164591761165461 683650285579695120 189492718025441376 798868544303095143 466621186424167115 278738156450563094 980180406033168802 529684448119147768 654670320204128588 624010761418349898 749625023424047493 378805570504406264 396901909344620599 50151332535745171 312907014...
output:
703347348
result:
ok 1 number(s): "703347348"
Test #30:
score: 0
Accepted
time: 183ms
memory: 7976kb
input:
299965 488779664960818182 684881461709239152 370772733008246945 973262531086872651 339038053504086716 487925616228248121 458997198111905119 193918773124889772 901847267815510491 392973794435356314 202763587580953756 91964676866525118 121844804459428412 982627328649422109 443679004199023457 195028727...
output:
583919761
result:
ok 1 number(s): "583919761"
Test #31:
score: 0
Accepted
time: 171ms
memory: 7904kb
input:
292643 885933786571718881 408853069123939984 579863120618091871 725595629953964715 551492441973118306 213619989431391568 504966209328764750 235368742076822666 122046100493501455 115029290569010363 661401670878683404 3665903534295425 919718453348795357 599431703853111722 445262758616102479 6860658467...
output:
387977592
result:
ok 1 number(s): "387977592"
Test #32:
score: 0
Accepted
time: 183ms
memory: 7964kb
input:
292491 763743652658146112 102806465022787187 315466265542596832 999824726308282557 572491004307851676 796097105124426022 247523047839726865 621368381286448220 950998245722045318 563822606683198330 611127711288603969 1000000000000000000 108497972616311593 0 82995099000145860 0 659887538894318973 9349...
output:
709594681
result:
ok 1 number(s): "709594681"
Test #33:
score: 0
Accepted
time: 183ms
memory: 8028kb
input:
299438 1000000000000000000 669109485744875663 415499033356488591 510327021619837306 317270410305894535 746492389692196787 641234759772343223 285976455008449868 922809245657738289 455695129000230785 730205749716839604 13915248131148301 647848941873902333 365588551564816876 706334453258635769 77501293...
output:
127652736
result:
ok 1 number(s): "127652736"
Test #34:
score: 0
Accepted
time: 184ms
memory: 7996kb
input:
295990 74919922975719931 556570590345288886 384903559146445415 810529063929528474 659397711202572252 227196167440135480 83112090739411281 842297603524569921 651269742053427127 83831186954045971 854509515214099805 323877107990151124 254381925956059641 735593636816998223 929166467098427539 97218767371...
output:
550991522
result:
ok 1 number(s): "550991522"
Test #35:
score: 0
Accepted
time: 102ms
memory: 8004kb
input:
299026 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 112ms
memory: 7952kb
input:
300000 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 5497558138...
output:
134043129
result:
ok 1 number(s): "134043129"
Test #37:
score: 0
Accepted
time: 148ms
memory: 7716kb
input:
300000 999999999999729004 999999999999811306 999999999999836828 999999999999938680 999999999999819432 999999999999887166 999999999999897439 999999999999703079 999999999999706316 999999999999793309 999999999999844830 999999999999854182 999999999999885704 999999999999993442 999999999999777305 99999999...
output:
30752309
result:
ok 1 number(s): "30752309"
Extra Test:
score: 0
Extra Test Passed