QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#874123#1318. 易见wjwweiwei100 ✓523ms216660kbC++141.1kb2025-01-27 16:34:422025-01-27 16:34:43

Judging History

This is the latest submission verdict.

  • [2025-01-27 16:34:43]
  • Judged
  • Verdict: 100
  • Time: 523ms
  • Memory: 216660kb
  • [2025-01-27 16:34:42]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,B=27,P=1e9+7;
using ll=long long;
int n,a[N],q;
int sua[N][B],cura[B][B],curb[B][B],tag[N][B];
inline int mol(int x,int y){return x+y>=P?x+y-P:x+y;}
inline void Add(int &u,int v){u=mol(u,v);}
inline void chg(int &u){
	(u>=P)&&(u-=P);
	(u<0)&&(u+=P);
}
inline int tim(int x,int y){return 1ll*x*y%P;}
string s;
void build(){
	for(int i=0;i<B;i++){
		cura[i][i]=curb[i][i]=1;sua[0][i]=1;
	}
	for(int i=1;i<=n;i++){
		int c=s[i]-'a';
		for(int j=0;j<B;j++){
			sua[i][j]=sua[i-1][j]*2-cura[c][j];chg(sua[i][j]);
			cura[c][j]=sua[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
		int c=s[i]-'a';
		for(int j=0;j<B;j++){
			tag[i][j]=curb[j][c];
			curb[j][c]=curb[j][c]*2-tag[i-1][j];
			chg(curb[j][c]);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s;n=s.length();s="*"+s;
	build();
	cin>>q;
	int l,r;
	for(int i=0;i<=n;i++){
		for(int j=0;j<B;j++)chg(tag[i][j]=-tag[i][j]);
	}
	while(q--){
		cin>>l>>r;
		int ans=sua[r][B-1]-1;
		for(int j=0;j<B-1;j++)Add(ans,tim(sua[r][j],tag[l-1][j]));
		cout<<ans<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 14ms
memory: 7780kb

input:

caebggfgf
100000
1 1
3 4
6 9
1 2
1 6
4 5
9 9
4 6
7 7
1 2
2 7
1 1
4 6
1 4
6 7
1 9
1 3
7 8
1 9
1 1
8 8
2 4
1 7
1 6
4 6
1 5
1 4
2 4
5 9
2 7
8 9
7 8
3 7
1 4
1 7
1 1
6 8
3 7
5 5
1 7
4 7
3 3
2 6
1 9
2 5
7 7
4 7
1 7
1 8
7 9
1 4
6 9
4 7
4 6
1 8
1 7
4 9
4 9
7 8
2 5
2 3
5 7
5 6
1 1
3 5
4 9
1 3
3 8
1 4
1 4
3 8...

output:

1
3
11
3
47
3
1
5
1
3
47
1
5
15
3
271
7
3
271
1
1
7
95
47
5
31
15
7
16
47
3
3
23
15
95
1
6
23
1
95
11
1
23
271
15
1
11
95
159
6
15
11
11
5
159
95
33
33
3
15
3
5
2
1
7
33
7
39
15
15
39
1
31
95
1
23
95
31
5
33
47
1
1
31
11
5
1
7
31
31
95
95
15
159
47
1
1
95
39
5
3
1
3
39
1
15
1
15
31
271
3
19
1
79
95
...

result:

ok 100000 lines

Test #2:

score: 10
Accepted
time: 16ms
memory: 7784kb

input:

gaddaggffiiaibcgdgcf
100000
4 6
7 12
2 17
2 14
9 18
11 15
1 17
1 13
1 19
5 11
1 17
5 11
12 15
9 11
6 13
11 17
12 20
8 15
2 8
1 18
5 9
13 13
5 11
19 20
1 1
7 11
6 18
5 13
7 12
1 7
10 16
8 17
14 16
11 13
1 1
1 5
1 2
5 5
3 9
17 19
3 12
3 13
5 11
16 16
5 13
8 17
12 16
1 18
1 5
1 4
13 13
6 9
4 17
8 17
1 ...

output:

7
35
15599
1955
559
27
30241
1895
102007
53
30241
53
15
5
89
111
431
119
65
52899
17
1
53
3
1
17
2511
177
35
63
79
479
7
6
1
21
3
1
53
7
320
533
53
1
177
479
31
52899
21
11
1
8
5678
479
52899
1895
21
559
161
53
11
1435
11
191
1
5
1
159
39
1895
1895
19
3
7583
5
8517
7
111
8517
575
6
7
296
3791
3
3
18...

result:

ok 100000 lines

Test #3:

score: 10
Accepted
time: 16ms
memory: 7652kb

input:

ciddbdibiiedfdhfabfhhfbighgehfacefbdcaddihfcbggddbgceihigachhibbhebfhedieecififfahhehddihcebbciiiecabdbdagdhifeahicfhibfehffaifcggiahafhcfaibeeaehfdffhhdcgicfeehfghihcadddihfcbebddchhefhahiaidgiehhggbbihifdgaefecehdhhfbgghhdfdiecdegdihebbhcfcigcbafacfdfaebcfbcfeddhfchhbfedefdifdieebgaifdffcdddefaehg...

output:

926734056
535848361
908357516
644817911
809951961
627101129
84226139
5
284511473
992792034
809466284
499556255
754377895
629418276
230287488
179108215
72947822
679907782
422966486
401375261
888871632
2723846
624493564
542948168
104856630
604852785
882636607
468952009
959979632
565356813
733384463
17...

result:

ok 100000 lines

Test #4:

score: 10
Accepted
time: 18ms
memory: 7888kb

input:

bigfahbaffbbcaebaddbcgdgaggfaahaghgggeeicaghcbeaibiiifbbafhfdegfaddchcaggeidfdiiadchccdhcgfadgghigbadagabdcfeiefidihachfahaacgecagahddegefgabciigacfcihfggiehhihagdcgiehiaeddbhbecidcibhbfeihdfghcbfgigeggaidaadciadabdebdfefibaehbfgceeeifcicbfccfgafagcffbfcedgabbhdgfeaceadcecdaeibiiaeahhdfabhihhfhdgfga...

output:

173499273
526942899
72948438
392734942
86321595
391770791
504344786
720817535
346927789
911294547
324069699
491457204
251662673
109748006
133795099
565014756
833150907
652997640
764804131
333595032
379110142
455102773
962066608
665105558
794783287
236738344
407879987
539911400
200568524
815301830
56...

result:

ok 100000 lines

Test #5:

score: 10
Accepted
time: 19ms
memory: 10856kb

input:

fcbhhefdfeibfdcdeciafddcfcccfdehgcdffbcgbccdbaggifdefafegegffghifhfheeebfgehagdfafaiaaehciadidhdbhbfeidbcbdgebddedbdhbdfebeahhdbfbbfigdhcebhaadbhfabhbaddabhbgbigcigehihggchgfgecbadfidbcgfdchacfeiieiibeigfhiccdegchcehhghadfibihiddhagghddcggidhiiafcfaebcfdcfddhgbedhacbeahfbccfafadigbggfbcchgecadihbcec...

output:

833209166
228105950
931261465
489959181
475344880
890750623
519690448
872010477
174249958
391735836
686724729
165739420
334539260
950246672
183694978
920354447
165535076
514071509
612950854
292457643
606811886
16233946
756294113
805941470
648512105
181348450
410268207
783118597
871857102
326755240
8...

result:

ok 100000 lines

Test #6:

score: 10
Accepted
time: 17ms
memory: 10308kb

input:

hhhhcgghagheeiiiihchcdiidhgcecabciecehfacifbffgbddcbiifififhieifbciedbcaedhfgfefcggghbchbfiggeifabhddeddbidiiegahffeagefddccdgedbceidaidebcafcihhceififdfeheeabifeiihbibfcggebgfacfadfcgiebhefgcdfdefeeccaiifchdbbfghdidfbegecghhiigheehicaibdhfadghddaiaceddfhgfeahbbbgafdhggedbigcagdihffdhghbhiehabdaidaf...

output:

821260570
906777861
623629440
727938811
199843596
472546468
352748905
238114204
332489645
287573165
912182443
379624808
388634999
502115749
742082655
51838683
841693857
990972926
508201007
2008376
608750111
216742506
561452318
432793666
926110829
790819774
456009714
880808111
241462257
833374643
658...

result:

ok 100000 lines

Test #7:

score: 10
Accepted
time: 25ms
memory: 14632kb

input:

gacegeeedcigfbdadabhdegeiafeeicaifddhbhdbfgcgeiagficgehfgdhfhhcigdehgabhcgbchcfchgaadagigdfagbibdiifbibhdehhfagiddacdebegfgahebdghbigeaiiegcebfhbggadcgcdidaggbfhbhagaabbceiigbdgihgfcbacidageacdegabafbgfeidgicgahceeddieiecfcgcahhecihbgegagbibgghgcfhgfghfbdcgibaggcacbcfbcgcifbihdbbifacgbidicifgeahffch...

output:

604253627
159896614
252843796
540900319
232391213
751155218
528917611
402186120
787497939
795946542
321263740
865442829
256490410
710127099
382640936
155669808
302762394
101708040
826139232
501726207
606039275
969296410
275277294
173733678
287441011
340698778
692045171
272101517
277885850
124587057
...

result:

ok 100000 lines

Test #8:

score: 10
Accepted
time: 30ms
memory: 18860kb

input:

igiegdabdiagbacgbhacchiddchghgdedeahegifgifeghfcfcgbgffgdiegebafbbbdcidgfaccdafhicffcgdbgfbcdhddbidfedcdbahecffhafcdahadhahbacgcgihbbigeccgchbfdiecabbgcbahebfiighahbbdegibfebeahhcifciaccfddcfcehfidfbchcgffaibicighbcdhgbicdehadgegdggecehgdcacefahhiibdfghagbgbeiecabhbgecbgabbgaachaibhbdcecfigebicgieie...

output:

935271196
932711320
411951608
790449351
243569500
173761485
640592829
507748928
820482241
776092386
833810625
531760592
665611744
542591292
140411981
253318084
51095452
381071496
221389444
196866417
550066062
92855481
951726087
323796548
585988863
82469466
815432712
179476989
464177185
721266924
262...

result:

ok 100000 lines

Test #9:

score: 10
Accepted
time: 517ms
memory: 216660kb

input:

smiywmaxuhgqplxawtwvcikdgtlzfyqyvdymzhbzaedoxokdmrnayridmjoprmcdbnqihnujifivtoutqhrhondkimclxrhaaotmpvdoikausakkeugqhoyslngtdemktxrqxwqmscrvckhlhzmrsigwruehcijklvjytvkzsvcanjoqdzsykwvsuwybsaezqywakgeupfmdtkjktzkocpwkddfledimmwpiuryuxykcdgwpwpjnikafpwkqosbycjlcumcqaweyqvqhevojxbwryitguqwrzkehzxyoclgz...

output:

1
1
1
839337206
1
1
417680229
1
684348835
763314764
155844528
161507189
1
709993043
682124252
1
1
1
304122801
759759138
747141527
1
674570951
516380152
1
1
305868112
782342591
444310143
674997267
147433079
125798329
1
601927470
639128982
1
38222758
1
540644206
139579292
644516822
1
454523173
1440512...

result:

ok 1000000 lines

Test #10:

score: 10
Accepted
time: 523ms
memory: 215664kb

input:

qejgvyklefzqevwgumepmvhrrrdogmpalkxldleycdgfazbqmbzlqijqqnqfxxxzwydvcmezeitjneihzcbscqlmxavarqiyyczjzvohorhrqoiebzhtepkozkkzkwlgqeylafafsuzdpgndncbnijwmwvrsdvymfiwgrgjftrjgpzmchmzrtogjwxfqjidrjqlhlhirifwcfuqlezxviqtbhfvzghphdusdrypthixqhemwqzevpcwykenluyidqrissluvprbizdpruxfcmrylmdojlfspwvmwgassdrbo...

output:

768912220
631505024
1
1
142051055
1
1
565488031
1
1
432297965
699879763
1
894813353
1
924018902
1
1
861942205
1
1
805699924
1
429045845
673660833
481943702
160987166
1
70829901
1
546358627
1
669649199
1
1
1
1
519360474
1
1
1
1
1
1
1
140819607
810073728
489366762
1
120552837
516686504
1
1
1
590576128...

result:

ok 1000000 lines

Extra Test:

score: 0
Extra Test Passed