QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#442682#8520. Xor Partitionsucup-team3890#AC ✓180ms7380kbC++14771b2024-06-15 13:15:402024-06-15 13:15:41

Judging History

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

  • [2024-06-15 13:15:41]
  • 评测
  • 测评结果:AC
  • 用时:180ms
  • 内存:7380kb
  • [2024-06-15 13:15:40]
  • 提交

answer

#include <iostream>

constexpr int mod = 0x3b9aca07;
int n;
long long a[300007];

int dp[300007];
int sdp[67][2];

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> n;
  dp[0] = 1;
  for (int i = 0; i < 60; ++i) {
    sdp[i][0] = 1;
  }
  for (int i = 1; i <= n; ++i) {
  	std::cin >> a[i]; 
    for (int j = 0; j < 60; ++j) {
      if ((a[i] >> j) & 1) {
        std::swap(sdp[j][0], sdp[j][1]);
      }
      dp[i] = (dp[i] + ((__int128(1) * sdp[j][1]) << j)) % mod;
      if (dp[i] >= mod) {
        dp[i] -= mod;
      }
    }
    for (int j = 0; j < 60; ++j) {
      sdp[j][0] += dp[i];
      if (sdp[j][0] >= mod) {
        sdp[j][0] -= mod;
      }
    }
  }
  std::cout << dp[n] << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

4
7 3 1 2

output:

170

result:

ok 1 number(s): "170"

Test #2:

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

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 0ms
memory: 5552kb

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: 5648kb

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: 5612kb

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: 5612kb

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: 5676kb

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: 5620kb

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: 6ms
memory: 3976kb

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: 60ms
memory: 6092kb

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: 5868kb

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: 169ms
memory: 7008kb

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: 179ms
memory: 7304kb

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: 168ms
memory: 7084kb

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: 178ms
memory: 7104kb

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: 164ms
memory: 7016kb

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: 175ms
memory: 7136kb

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: 167ms
memory: 7104kb

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: 180ms
memory: 7128kb

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: 175ms
memory: 7132kb

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: 170ms
memory: 7380kb

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: 179ms
memory: 7072kb

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: 169ms
memory: 7040kb

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: 168ms
memory: 7340kb

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: 176ms
memory: 7052kb

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: 179ms
memory: 7124kb

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: 175ms
memory: 7132kb

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: 168ms
memory: 7024kb

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: 167ms
memory: 7016kb

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: 168ms
memory: 7020kb

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: 174ms
memory: 7032kb

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: 126ms
memory: 7364kb

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: 143ms
memory: 7132kb

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: 161ms
memory: 7076kb

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