ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183249 | #3289. 序列划分 | Hurry | 100 | 1554ms | 35860kb | C++11 | 1.4kb | 2023-08-08 11:47:04 | 2023-08-08 12:40:51 |
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
发现一些东西
一共只会有n个异或值会产生贡献,即
1~i的异或和(设为x)
然后的话可以统计以0结尾的或者以x结尾的,每一段都是x的方案数
f[i][0/1]直接继承
统计答案的话直接看后缀异或和即可
现在有一个问题就是如果出现了前缀异或和为0的
则所有f[i][0]都要加上f[i][1]
直接打全局标记和局部标记,每次询问到x的时候就把局部标记加到全局
*/
const int N=2e6+5,mo=1e9+7;
int f[N][2],tag[N],altag,n,a[N],ans,sufsum[N];
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%mo;
a=(a*a)%mo;
b>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--)sufsum[i]=sufsum[i+1]^a[i];
int sum=0;
for(int i=1;i<n;i++){
sum^=a[i];
if(sum==0){
altag++;
int x=sufsum[i+1];
f[x][0]=(f[x][0]+(((altag-tag[x])*f[x][1])%mo))%mo;
ans=(ans+(((altag-tag[x])*f[x][1])%mo))%mo;
tag[x]=altag;
}
else {
f[sum][0]=(f[sum][0]+(((altag-tag[sum])*f[sum][1])%mo))%mo;
tag[sum]=altag;
f[sum][1]=(f[sum][1]+f[sum][0]+1)%mo;
if(sufsum[i+1]==sum){
ans=(ans+f[sum][0]+1)%mo;
}
}
}
sum^=a[n];
ans=(ans+1)%mo;
ans=(ans+(sum==0?(qpow(2,altag)-1):0))%mo;
cout<<ans<<"\n";
}
/*
5
3 3 3 3 3
*/
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 3ms
memory: 3856kb
input:
91 570866 419975 375843 577809 803790 330729 25119 678100 37965 859554 945849 206333 220728 722925 7...
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 3ms
memory: 4060kb
input:
96 574106 196215 121820 679290 662787 148938 967422 495394 44894 862985 862985 282148 579710 824922 ...
output:
65615
result:
ok 1 number(s): "65615"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3904kb
input:
99 171082 520749 71456 293191 229481 38881 74890 669551 844811 319590 0 52520 774069 143636 60652 27...
output:
16777290
result:
ok 1 number(s): "16777290"
Test #4:
score: 0
Accepted
time: 3ms
memory: 4052kb
input:
97 0 904400 290882 583284 763251 720789 875844 875844 355670 355670 0 668002 340419 983201 83698 300...
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
92 0 183218 533248 828267 793598 675879 4689 581442 277070 566209 283804 0 0 537331 581325 329631 36...
output:
536870974
result:
ok 1 number(s): "536870974"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
91 218725 218725 806491 806491 692483 502195 317422 651102 32490 32490 935679 611238 581493 424009 5...
output:
1048646
result:
ok 1 number(s): "1048646"
Test #7:
score: 0
Accepted
time: 2ms
memory: 4032kb
input:
92 702156 41093 600243 110993 801974 202858 895927 202129 833366 801623 186537 436927 170740 873501 ...
output:
65611
result:
ok 1 number(s): "65611"
Test #8:
score: 0
Accepted
time: 3ms
memory: 3932kb
input:
97 416596 899612 778568 937437 286397 384191 376523 123360 836867 431947 115388 0 807766 368497 6420...
output:
1048652
result:
ok 1 number(s): "1048652"
Test #9:
score: 0
Accepted
time: 3ms
memory: 3884kb
input:
91 0 705759 234276 531283 85160 0 793893 35361 269016 847987 294319 334900 334900 366794 734590 8057...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 3ms
memory: 4044kb
input:
100 230382 564319 280936 859747 149690 0 219019 294627 513087 64855 546772 342581 880097 143027 3443...
output:
16777291
result:
ok 1 number(s): "16777291"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
99 0 0 0 0 928561 555762 328711 25104 210900 928561 0 884469 189938 597024 784850 0 189938 516597 16...
output:
4598606
result:
ok 1 number(s): "4598606"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
100 103127 0 0 0 103127 0 815745 274979 475516 983518 839027 249005 0 983518 0 935473 797262 666845 ...
output:
38562
result:
ok 1 number(s): "38562"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
96 0 0 334042 0 644873 784463 472988 472988 640073 979925 0 687553 438802 839635 751144 803252 47298...
output:
292203
result:
ok 1 number(s): "292203"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
96 943369 182615 182615 243647 905910 830558 26170 0 838244 943369 943369 371098 591300 869694 19082...
output:
80
result:
ok 1 number(s): "80"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
93 851735 397019 208977 639389 276791 880662 243949 486059 891751 276791 276791 639389 208977 486059...
output:
8917120
result:
ok 1 number(s): "8917120"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
90 276224 990145 120352 0 0 167495 554150 69866 615500 554150 0 719585 780811 615500 718871 63488 65...
output:
242255
result:
ok 1 number(s): "242255"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
99 952499 0 955437 324933 930656 706085 777324 0 330882 969840 969840 17603 952499 0 322011 680296 3...
output:
135022257
result:
ok 1 number(s): "135022257"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
92 0 54201 583370 715742 134420 410805 431884 537971 0 0 537971 15437 189152 560822 675867 0 537971 ...
output:
268667848
result:
ok 1 number(s): "268667848"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
91 239801 633113 802534 378453 653491 280982 280982 946068 290356 279884 162314 409414 0 655776 9541...
output:
134330452
result:
ok 1 number(s): "134330452"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
100 0 804323 327817 830315 0 388609 0 99024 196416 196416 788362 551771 290001 252367 0 207091 95212...
output:
35112038
result:
ok 1 number(s): "35112038"
Subtask #2:
score: 20
Accepted
Test #21:
score: 20
Accepted
time: 2ms
memory: 3412kb
input:
1946 0 0 1743 1743 767 238 529 1999 824 313 1486 0 437 1424 1649 302 0 1249 1947 965 965 0 0 1234 16...
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
1992 1081 337 1171 11 1183 1969 734 1883 1883 172 1270 1146 32 1894 270 23 1663 0 0 1278 1177 103 49...
output:
582326192
result:
ok 1 number(s): "582326192"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1921 1010 131 74 79 884 879 562 551 0 1733 1471 199 199 803 873 805 76 803 0 1379 1479 1084 1176 0 0...
output:
662707644
result:
ok 1 number(s): "662707644"
Test #24:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
1944 1541 1140 753 1934 204 286 130 1630 133 1429 137 1886 1536 1450 365 40 484 1788 790 1062 0 1891...
output:
731420692
result:
ok 1 number(s): "731420692"
Test #25:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1946 515 233 549 207 109 1284 1385 986 608 442 1910 1627 1282 1043 667 363 1099 1 1256 1259 1770 217...
output:
21442284
result:
ok 1 number(s): "21442284"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1980 450 651 841 501 1007 673 187 0 1966 1966 439 439 722 702 1954 6 1992 0 1001 1001 0 636 164 1028...
output:
170182614
result:
ok 1 number(s): "170182614"
Test #27:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
1903 1197 1375 498 1609 1841 1087 951 1599 188 115 1095 1095 815 364 1857 1233 37 0 1162 1884 544 26...
output:
296933091
result:
ok 1 number(s): "296933091"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
1975 56 460 0 676 399 333 1419 1727 1578 1596 1912 331 0 121 914 1384 0 0 0 98 679 1900 1255 1350 17...
output:
747492943
result:
ok 1 number(s): "747492943"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1900 436 436 1035 29 305 1973 658 0 958 1031 1977 715 534 1222 1251 887 911 444 444 129 687 378 818 ...
output:
164
result:
ok 1 number(s): "164"
Test #30:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
2000 932 874 191 778 910 732 1827 74 904 1323 621 1181 1866 340 74 1235 0 1940 238 1091 1197 1089 63...
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
1988 1200 1200 1504 1504 1504 1504 1613 941 941 930 1519 0 1297 1417 152 152 1376 1528 819 228 709 2...
output:
640800632
result:
ok 1 number(s): "640800632"
Test #32:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1929 1741 1741 0 0 484 1191 1544 517 334 1619 598 1029 976 976 1619 1619 1237 657 1847 1568 256 1184...
output:
240980623
result:
ok 1 number(s): "240980623"
Test #33:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
1948 938 605 503 1730 1244 1759 1763 546 414 414 38 0 641 641 201 742 83 602 1644 721 1815 1384 1884...
output:
490842795
result:
ok 1 number(s): "490842795"
Test #34:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
1944 667 783 404 1810 1411 920 412 149 1664 837 423 720 1714 1122 1122 1134 287 611 880 1156 230 172...
output:
270363962
result:
ok 1 number(s): "270363962"
Test #35:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
1983 1734 1232 534 860 330 534 377 607 806 0 1050 728 723 1148 830 851 109 362 584 345 1755 1229 173...
output:
203547510
result:
ok 1 number(s): "203547510"
Test #36:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
1982 0 460 460 141 141 0 1930 1009 760 760 0 1147 1692 278 1866 1211 1376 283 460 1606 663 0 1224 12...
output:
460771022
result:
ok 1 number(s): "460771022"
Test #37:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
1965 391 5 386 1928 535 1203 454 1493 1098 1719 1142 563 853 853 377 1906 1932 0 0 0 1872 0 1966 185...
output:
663249920
result:
ok 1 number(s): "663249920"
Test #38:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
1948 1658 1658 740 898 1820 165 425 1426 740 0 1562 1916 414 1948 1841 19 1007 1735 1390 1687 481 19...
output:
932491841
result:
ok 1 number(s): "932491841"
Test #39:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
1992 887 675 468 0 0 1871 58 1273 908 1183 1774 1574 802 0 1909 402 70 847 46 1450 1001 105 1183 182...
output:
838116677
result:
ok 1 number(s): "838116677"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
1969 674 1136 1746 0 1032 1998 1353 1679 787 787 1911 74 434 472 0 1879 680 1063 434 956 376 708 135...
output:
455469201
result:
ok 1 number(s): "455469201"
Subtask #3:
score: 20
Accepted
Test #41:
score: 20
Accepted
time: 9ms
memory: 15532kb
input:
2970 0 302893 302893 135509 799036 925801 758389 951791 843922 731356 188372 420965 313961 536897 19...
output:
516574510
result:
ok 1 number(s): "516574510"
Test #42:
score: 0
Accepted
time: 3ms
memory: 15416kb
input:
2929 667748 546788 250407 501136 397367 0 130705 352301 302780 240909 385596 858723 491647 167465 94...
output:
1
result:
ok 1 number(s): "1"
Test #43:
score: 0
Accepted
time: 7ms
memory: 15448kb
input:
2931 612419 612419 729030 729030 9059 425706 712158 819287 848741 41130 807887 916660 731249 841346 ...
output:
39727419
result:
ok 1 number(s): "39727419"
Test #44:
score: 0
Accepted
time: 2ms
memory: 15688kb
input:
2952 0 0 541332 567373 128720 92699 30226 443214 302878 154704 0 699696 915379 733866 863714 697423 ...
output:
759933285
result:
ok 1 number(s): "759933285"
Test #45:
score: 0
Accepted
time: 9ms
memory: 15644kb
input:
2968 446793 734080 335404 494181 255582 823518 692016 738967 549893 211296 353429 797567 176242 1288...
output:
761487170
result:
ok 1 number(s): "761487170"
Test #46:
score: 0
Accepted
time: 11ms
memory: 15992kb
input:
2999 276199 866479 593480 690820 876662 31813 520940 154590 260868 115841 371563 553311 130114 96121...
output:
1
result:
ok 1 number(s): "1"
Test #47:
score: 0
Accepted
time: 4ms
memory: 15756kb
input:
2944 376136 164501 475101 701418 698725 6799 0 705407 705407 691873 21794 534991 193100 536310 80643...
output:
782973049
result:
ok 1 number(s): "782973049"
Test #48:
score: 0
Accepted
time: 4ms
memory: 15556kb
input:
2931 326524 326524 609847 972247 344610 978971 307980 281363 247520 866289 927416 788079 579469 8574...
output:
1
result:
ok 1 number(s): "1"
Test #49:
score: 0
Accepted
time: 2ms
memory: 15608kb
input:
2982 575343 697654 732945 693517 722745 581500 553638 5110 770318 237662 504122 483206 573293 399595...
output:
734998462
result:
ok 1 number(s): "734998462"
Test #50:
score: 0
Accepted
time: 2ms
memory: 15624kb
input:
2912 741981 364995 884345 978455 696311 840432 287001 564897 751624 928078 603460 839355 879063 3828...
output:
565944503
result:
ok 1 number(s): "565944503"
Test #51:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
2968 14639 466364 286407 576156 766152 960860 200851 899535 351652 925775 753131 870675 720703 50538...
output:
691869248
result:
ok 1 number(s): "691869248"
Test #52:
score: 0
Accepted
time: 3ms
memory: 3964kb
input:
2971 423153 885759 142795 645829 769281 437870 855962 7413 624058 0 777444 694237 577155 39904 39904...
output:
802796869
result:
ok 1 number(s): "802796869"
Test #53:
score: 0
Accepted
time: 3ms
memory: 3916kb
input:
2922 719660 452143 411203 700557 60365 976452 576052 404592 691671 853292 493819 493819 493819 0 515...
output:
591503901
result:
ok 1 number(s): "591503901"
Test #54:
score: 0
Accepted
time: 3ms
memory: 3828kb
input:
2995 376870 876044 722089 746419 26394 663179 845599 894981 964885 0 844863 699274 771812 906509 937...
output:
91372150
result:
ok 1 number(s): "91372150"
Test #55:
score: 0
Accepted
time: 3ms
memory: 3932kb
input:
2944 234242 498792 25920 975019 549997 192236 628083 639745 576524 430098 920172 289322 289322 0 781...
output:
550762153
result:
ok 1 number(s): "550762153"
Test #56:
score: 0
Accepted
time: 3ms
memory: 3920kb
input:
2910 0 896018 914188 175288 163808 35910 0 625153 621624 63033 993248 541011 548887 984740 25890 133...
output:
827002781
result:
ok 1 number(s): "827002781"
Test #57:
score: 0
Accepted
time: 3ms
memory: 3932kb
input:
2959 518625 518625 603550 132538 698933 104977 454818 901254 654328 744487 735351 176012 603550 6035...
output:
248750423
result:
ok 1 number(s): "248750423"
Test #58:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
2920 536125 536125 375753 395821 649024 418090 694124 434402 410051 275225 274192 563937 793079 1881...
output:
41931411
result:
ok 1 number(s): "41931411"
Test #59:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
2960 634142 478720 416376 844306 987917 739449 975646 975646 285556 285556 523571 0 605050 605050 36...
output:
795876447
result:
ok 1 number(s): "795876447"
Test #60:
score: 0
Accepted
time: 3ms
memory: 3916kb
input:
2904 170172 208916 78688 39880 737839 932133 316322 67695 41159 417060 174065 174065 686247 796035 3...
output:
938730769
result:
ok 1 number(s): "938730769"
Subtask #4:
score: 40
Accepted
Test #61:
score: 40
Accepted
time: 79ms
memory: 35632kb
input:
493900 281750 307734 208258 786738 553314 745535 116722 223658 110235 772553 370475 658134 763802 76...
output:
1
result:
ok 1 number(s): "1"
Test #62:
score: 0
Accepted
time: 86ms
memory: 35704kb
input:
497958 56023 798539 23388 194308 940484 859173 741579 108990 661478 104829 814027 134091 496220 1787...
output:
552358079
result:
ok 1 number(s): "552358079"
Test #63:
score: 0
Accepted
time: 74ms
memory: 35768kb
input:
494743 579935 579935 0 316722 48014 913350 799468 647081 288776 475709 886492 768808 621566 0 289097...
output:
1
result:
ok 1 number(s): "1"
Test #64:
score: 0
Accepted
time: 76ms
memory: 35672kb
input:
496255 80177 671817 751992 126730 462281 451267 226265 902293 539014 860159 611520 181749 354750 354...
output:
434279046
result:
ok 1 number(s): "434279046"
Test #65:
score: 0
Accepted
time: 92ms
memory: 35860kb
input:
499687 687940 687940 397514 316582 57941 808359 947102 553802 776353 516511 57414 895613 589903 3115...
output:
1
result:
ok 1 number(s): "1"
Test #66:
score: 0
Accepted
time: 79ms
memory: 35628kb
input:
494524 489202 489202 95313 792396 143516 288690 734259 866997 687692 873977 51655 710855 941539 6307...
output:
776536617
result:
ok 1 number(s): "776536617"
Test #67:
score: 0
Accepted
time: 85ms
memory: 35708kb
input:
491536 24564 750729 405722 526137 335006 382548 382548 0 604826 604826 123183 975534 28424 24720 368...
output:
114949933
result:
ok 1 number(s): "114949933"
Test #68:
score: 0
Accepted
time: 86ms
memory: 35684kb
input:
491863 586229 877186 110511 426521 179905 877869 439546 774615 0 484559 558889 104340 3590 948852 22...
output:
644679469
result:
ok 1 number(s): "644679469"
Test #69:
score: 0
Accepted
time: 85ms
memory: 35676kb
input:
490592 0 846555 485079 740103 254533 640858 491273 486076 718753 0 44071 842453 667708 428004 627017...
output:
1
result:
ok 1 number(s): "1"
Test #70:
score: 0
Accepted
time: 82ms
memory: 35628kb
input:
493068 930717 499851 627478 414134 957825 132958 115824 182766 934764 864121 34859 451304 298384 103...
output:
857005545
result:
ok 1 number(s): "857005545"
Test #71:
score: 0
Accepted
time: 58ms
memory: 16076kb
input:
497736 0 521508 923773 650585 962144 962144 133767 133767 725742 710613 341850 26141 961854 837216 6...
output:
99316243
result:
ok 1 number(s): "99316243"
Test #72:
score: 0
Accepted
time: 62ms
memory: 16236kb
input:
495606 0 712244 645364 634227 189064 543035 45057 45057 179630 179630 796263 796263 0 0 6248 204456 ...
output:
497167332
result:
ok 1 number(s): "497167332"
Test #73:
score: 0
Accepted
time: 56ms
memory: 16112kb
input:
499458 488467 287870 200813 939038 939038 0 12119 127553 872494 907828 842420 436836 888102 783055 8...
output:
440178720
result:
ok 1 number(s): "440178720"
Test #74:
score: 0
Accepted
time: 55ms
memory: 16032kb
input:
497739 339052 20262 416002 211528 209314 623563 701033 0 0 708607 708607 0 0 0 0 0 455184 222740 365...
output:
199885923
result:
ok 1 number(s): "199885923"
Test #75:
score: 0
Accepted
time: 49ms
memory: 16144kb
input:
495948 0 680446 355436 605349 8983 982621 432439 229743 0 799170 677587 758580 749621 749621 0 62901...
output:
988172913
result:
ok 1 number(s): "988172913"
Test #76:
score: 0
Accepted
time: 60ms
memory: 16212kb
input:
498727 0 892668 41424 868140 0 0 0 0 157892 637295 674143 104692 645325 299306 342784 553703 0 76715...
output:
356616381
result:
ok 1 number(s): "356616381"
Test #77:
score: 0
Accepted
time: 73ms
memory: 15952kb
input:
494255 211998 211998 0 941580 338596 610416 308261 87431 88803 776475 931188 226294 0 0 707172 95917...
output:
505209738
result:
ok 1 number(s): "505209738"
Test #78:
score: 0
Accepted
time: 50ms
memory: 15884kb
input:
491807 0 938212 310581 716241 933068 933068 992161 114506 957675 427973 526646 39189 912674 260804 9...
output:
791888614
result:
ok 1 number(s): "791888614"
Test #79:
score: 0
Accepted
time: 62ms
memory: 16016kb
input:
494651 625083 213052 508268 383166 577621 652593 750595 684852 859355 226489 432740 792424 9096 4015...
output:
349554344
result:
ok 1 number(s): "349554344"
Test #80:
score: 0
Accepted
time: 54ms
memory: 16108kb
input:
495891 489961 939809 691782 747680 269413 714576 93546 482929 677644 677644 547507 624640 0 781580 0...
output:
137059274
result:
ok 1 number(s): "137059274"