QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874123 | #1318. 易见 | wjwweiwei | 100 ✓ | 523ms | 216660kb | C++14 | 1.1kb | 2025-01-27 16:34:42 | 2025-01-27 16:34:43 |
Judging History
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