UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183249#3289. 序列划分Hurry1001554ms35860kbC++111.4kb2023-08-08 11:47:042023-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"