QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #199052 | #670. K-th String | pengpeng_fudan | AC ✓ | 3ms | 9908kb | C++14 | 1.3kb | 2023-10-03 20:38:04 | 2023-10-03 20:38:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
const ll mod=1e9+7;
int n,z;
string s;
int sz;
ll ans=0;
ll dp[30][30][1010];
void solve(int x) {
for(int i=0;i<=n;i++) for(int j=0;j<=sz;j++) for(int k=0;k<=z;k++) dp[i][j][k]=0;
int ni=sz-1;
int lw=s[1]-'a';
int ov=n-(s[1]-'a'+1);
for(int i=2;i<=sz;i++){
if(s[i]<s[1]){
ni+=n-(x+i-1)+1;
lw--;
}
else ov--;
}
//cout<<lw<<' '<<ov<<'\n';
if(ni>=z) return ;
dp[0][0][0]=1;
for(int i=1;i<=n-sz;i++){
for(int j=0;j<=lw;j++){
for(int k=0;k<=z-ni-1;k++){
if(i-j>ov||j>i) continue;
dp[i][j][k]=dp[i-1][j][k];
int ad=(i<x?n-i+1:n-(i+sz)+1);
if(j>=1&&k>=ad) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k-ad])%mod;
}
}
}
ll zp=1;
for(int i=1;i<=lw;i++) zp=zp*i%mod;
for(int i=1;i<=ov;i++) zp=zp*i%mod;
for(int i=0;i<=lw;i++) ans=(ans+dp[n-sz][i][z-ni-1]*zp%mod)%mod;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>z>>s;
s=' '+s;
sz=s.size()-1;
for(int i=1;i<=n-sz+1;i++) solve(i);
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5704kb
input:
7 12 caedgfb
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
2 3 b
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
8 4 febadh
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
4 9 bca
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
3 2 bc
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 5604kb
input:
8 8 acgefbdh
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
4 7 cb
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
8 36 hgfaec
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5676kb
input:
8 28 feadch
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
3 6 cba
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
8 24 fhgdce
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5496kb
input:
8 17 dhcfbae
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
8 26 ebcgdfha
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
2 2 ab
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 5520kb
input:
6 5 abdef
output:
2
result:
ok single line: '2'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
6 10 bfaecd
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
8 26 fgbceah
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5536kb
input:
8 8 afeghdbc
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
8 33 gaedbhfc
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
8 36 hdegbacf
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 3 ba
output:
1
result:
ok single line: '1'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #28:
score: 0
Accepted
time: 1ms
memory: 5520kb
input:
8 24 dafbge
output:
1
result:
ok single line: '1'
Test #29:
score: 0
Accepted
time: 1ms
memory: 5556kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #30:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
8 28 fahdecgb
output:
1
result:
ok single line: '1'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
2 2 b
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
8 14 beahcfdg
output:
1
result:
ok single line: '1'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
8 13 chfgebad
output:
1
result:
ok single line: '1'
Test #35:
score: 0
Accepted
time: 1ms
memory: 5592kb
input:
4 9 cad
output:
1
result:
ok single line: '1'
Test #36:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
8 19 dcghfbea
output:
1
result:
ok single line: '1'
Test #37:
score: 0
Accepted
time: 1ms
memory: 5480kb
input:
7 13 cagfde
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 0ms
memory: 5776kb
input:
8 15 caefdhg
output:
1
result:
ok single line: '1'
Test #39:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
8 6 agchbe
output:
6
result:
ok single line: '6'
Test #40:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
8 24 ecdgbf
output:
2
result:
ok single line: '2'
Test #41:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
5 9 dac
output:
1
result:
ok single line: '1'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
8 16 cgehaf
output:
1
result:
ok single line: '1'
Test #43:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
6 15 ebfd
output:
2
result:
ok single line: '2'
Test #44:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
8 31 gcdebh
output:
2
result:
ok single line: '2'
Test #45:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #46:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
8 12 bfheagcd
output:
1
result:
ok single line: '1'
Test #47:
score: 0
Accepted
time: 0ms
memory: 5552kb
input:
3 2 b
output:
2
result:
ok single line: '2'
Test #48:
score: 0
Accepted
time: 1ms
memory: 5648kb
input:
9 7 bcidafg
output:
0
result:
ok single line: '0'
Test #49:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2 1 a
output:
2
result:
ok single line: '2'
Test #50:
score: 0
Accepted
time: 0ms
memory: 8212kb
input:
18 94 pgamldbkqncrfeji
output:
0
result:
ok single line: '0'
Test #51:
score: 0
Accepted
time: 2ms
memory: 9644kb
input:
22 199 rilhdvfuecpbakjtoqsn
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
4 5 dba
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
2 1 ba
output:
0
result:
ok single line: '0'
Test #54:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
2 1 a
output:
2
result:
ok single line: '2'
Test #55:
score: 0
Accepted
time: 0ms
memory: 8848kb
input:
26 154 jrlnfwachzebpoktudivmqysxg
output:
1
result:
ok single line: '1'
Test #56:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 3 b
output:
2
result:
ok single line: '2'
Test #57:
score: 0
Accepted
time: 0ms
memory: 9156kb
input:
26 281 ucptxmzojbeygsqkadhvwrfnil
output:
1
result:
ok single line: '1'
Test #58:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
11 40 gbhiackjdfe
output:
1
result:
ok single line: '1'
Test #59:
score: 0
Accepted
time: 2ms
memory: 9032kb
input:
26 179 kobzgdjyticevuqwmprafhxnsl
output:
1
result:
ok single line: '1'
Test #60:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
5 5 bda
output:
2
result:
ok single line: '2'
Test #61:
score: 0
Accepted
time: 1ms
memory: 9824kb
input:
22 204 rkhtbvpgfqoudmjniaclse
output:
1
result:
ok single line: '1'
Test #62:
score: 0
Accepted
time: 1ms
memory: 7788kb
input:
16 95 lpnhgdmebjcoka
output:
2
result:
ok single line: '2'
Test #63:
score: 0
Accepted
time: 0ms
memory: 9752kb
input:
26 94 fczijtnmdoxeskhypwbvquglar
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 1ms
memory: 9792kb
input:
20 42 dskhoptejmnbcrgalqif
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
8 19 efhacd
output:
2
result:
ok single line: '2'
Test #66:
score: 0
Accepted
time: 0ms
memory: 5520kb
input:
1 1 a
output:
1
result:
ok single line: '1'
Test #67:
score: 0
Accepted
time: 2ms
memory: 8928kb
input:
26 148 lyvxhnpstqwfzjbdegumcakor
output:
1
result:
ok single line: '1'
Test #68:
score: 0
Accepted
time: 0ms
memory: 7724kb
input:
12 23 cfbgdahilj
output:
2
result:
ok single line: '2'
Test #69:
score: 0
Accepted
time: 2ms
memory: 9244kb
input:
26 311 wpiazehgvcsxjobrqfkmtldyun
output:
1
result:
ok single line: '1'
Test #70:
score: 0
Accepted
time: 0ms
memory: 9148kb
input:
26 302 vhixsutaewdlfrbjqmngczyokp
output:
1
result:
ok single line: '1'
Test #71:
score: 0
Accepted
time: 2ms
memory: 9032kb
input:
26 261 swtflxorcpehjdzguivkaqyb
output:
2
result:
ok single line: '2'
Test #72:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
10 49 iaejgcdfh
output:
1
result:
ok single line: '1'
Test #73:
score: 0
Accepted
time: 2ms
memory: 9908kb
input:
26 82 enyqsdujflzrcbwhgtaxkivopm
output:
1
result:
ok single line: '1'
Test #74:
score: 0
Accepted
time: 0ms
memory: 5560kb
input:
5 5 bed
output:
1
result:
ok single line: '1'
Test #75:
score: 0
Accepted
time: 2ms
memory: 9696kb
input:
26 96 fzrbpehcvywjgxknuoqtalimsd
output:
1
result:
ok single line: '1'
Test #76:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
10 14 bhdcjaige
output:
1
result:
ok single line: '1'
Test #77:
score: 0
Accepted
time: 0ms
memory: 9808kb
input:
26 342 yqsbrektndmxuolaivzfchgpw
output:
1
result:
ok single line: '1'
Test #78:
score: 0
Accepted
time: 0ms
memory: 7676kb
input:
13 16 bedigmalcfk
output:
2
result:
ok single line: '2'
Test #79:
score: 0
Accepted
time: 0ms
memory: 8868kb
input:
26 219 qzbgpfalmvdunjsotrcwkihe
output:
2
result:
ok single line: '2'
Test #80:
score: 0
Accepted
time: 2ms
memory: 8292kb
input:
22 56 dniktuajmpceqlbohrgs
output:
2
result:
ok single line: '2'
Test #81:
score: 0
Accepted
time: 2ms
memory: 8708kb
input:
26 77 dcgilpkznbrvuwehtaxmfyoqsj
output:
1
result:
ok single line: '1'
Test #82:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
5 3 ace
output:
6
result:
ok single line: '6'
Test #83:
score: 0
Accepted
time: 2ms
memory: 8940kb
input:
26 159 krzcwglqfjpbnaiumsyhdvotxe
output:
1
result:
ok single line: '1'
Test #84:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
3 1 a
output:
6
result:
ok single line: '6'
Test #85:
score: 0
Accepted
time: 2ms
memory: 8996kb
input:
26 251 tpvyjcaluxefgqwbnrmikszo
output:
2
result:
ok single line: '2'
Test #86:
score: 0
Accepted
time: 0ms
memory: 8152kb
input:
16 127 olbemcpafjndkgi
output:
1
result:
ok single line: '1'
Test #87:
score: 0
Accepted
time: 1ms
memory: 5488kb
input:
4 9 d
output:
6
result:
ok single line: '6'
Test #88:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
8 4 fg
output:
0
result:
ok single line: '0'
Test #89:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
8 19 g
output:
0
result:
ok single line: '0'
Test #90:
score: 0
Accepted
time: 1ms
memory: 5536kb
input:
6 14 dc
output:
16
result:
ok single line: '16'
Test #91:
score: 0
Accepted
time: 0ms
memory: 5640kb
input:
8 14 cefgd
output:
4
result:
ok single line: '4'
Test #92:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
8 24 fegb
output:
12
result:
ok single line: '12'
Test #93:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
8 14 d
output:
4320
result:
ok single line: '4320'
Test #94:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
8 14 cbhf
output:
18
result:
ok single line: '18'
Test #95:
score: 0
Accepted
time: 1ms
memory: 5500kb
input:
8 19 eb
output:
612
result:
ok single line: '612'
Test #96:
score: 0
Accepted
time: 1ms
memory: 5496kb
input:
5 5 b
output:
24
result:
ok single line: '24'
Test #97:
score: 0
Accepted
time: 1ms
memory: 5500kb
input:
8 6 be
output:
600
result:
ok single line: '600'
Test #98:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
8 16 degb
output:
16
result:
ok single line: '16'
Test #99:
score: 0
Accepted
time: 0ms
memory: 5572kb
input:
8 16 e
output:
2880
result:
ok single line: '2880'
Test #100:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
6 17 e
output:
96
result:
ok single line: '96'
Test #101:
score: 0
Accepted
time: 2ms
memory: 9620kb
input:
22 41 urbv
output:
0
result:
ok single line: '0'
Test #102:
score: 0
Accepted
time: 0ms
memory: 7680kb
input:
19 53 bksora
output:
0
result:
ok single line: '0'
Test #103:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
8 17 a
output:
0
result:
ok single line: '0'
Test #104:
score: 0
Accepted
time: 2ms
memory: 9740kb
input:
26 310 wxglnbcsfim
output:
707619005
result:
ok single line: '707619005'
Test #105:
score: 0
Accepted
time: 1ms
memory: 7584kb
input:
14 57 femchdbnlgj
output:
2
result:
ok single line: '2'
Test #106:
score: 0
Accepted
time: 2ms
memory: 7716kb
input:
26 190 n
output:
793426072
result:
ok single line: '793426072'
Test #107:
score: 0
Accepted
time: 1ms
memory: 7588kb
input:
19 177 q
output:
384492431
result:
ok single line: '384492431'
Test #108:
score: 0
Accepted
time: 2ms
memory: 7760kb
input:
26 148 lwu
output:
147045489
result:
ok single line: '147045489'
Test #109:
score: 0
Accepted
time: 1ms
memory: 7684kb
input:
14 62 i
output:
267468772
result:
ok single line: '267468772'
Test #110:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
14 48 ga
output:
327196800
result:
ok single line: '327196800'
Test #111:
score: 0
Accepted
time: 0ms
memory: 8228kb
input:
26 181 okvubjzwdxqmc
output:
432166393
result:
ok single line: '432166393'
Test #112:
score: 0
Accepted
time: 2ms
memory: 9652kb
input:
26 310 y
output:
576292958
result:
ok single line: '576292958'
Test #113:
score: 0
Accepted
time: 2ms
memory: 9852kb
input:
26 102 gmoecsvxbqfptdukwrnyaj
output:
24
result:
ok single line: '24'
Test #114:
score: 0
Accepted
time: 1ms
memory: 7840kb
input:
15 71 gdbjakomcle
output:
6
result:
ok single line: '6'
Test #115:
score: 0
Accepted
time: 0ms
memory: 7988kb
input:
26 94 hrjcuao
output:
922356513
result:
ok single line: '922356513'
Test #116:
score: 0
Accepted
time: 1ms
memory: 5488kb
input:
9 1 a
output:
362880
result:
ok single line: '362880'
Test #117:
score: 0
Accepted
time: 2ms
memory: 9872kb
input:
26 81 fbxgtinmuohswrk
output:
6773760
result:
ok single line: '6773760'
Test #118:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
15 76 jdlkiboacn
output:
48
result:
ok single line: '48'
Test #119:
score: 0
Accepted
time: 3ms
memory: 7800kb
input:
26 225 s
output:
298955907
result:
ok single line: '298955907'
Test #120:
score: 0
Accepted
time: 0ms
memory: 8040kb
input:
26 75 hysotxlfcg
output:
629258561
result:
ok single line: '629258561'
Test #121:
score: 0
Accepted
time: 2ms
memory: 9560kb
input:
26 169 p
output:
942577163
result:
ok single line: '942577163'
Test #122:
score: 0
Accepted
time: 1ms
memory: 7604kb
input:
14 88 kh
output:
89268480
result:
ok single line: '89268480'
Extra Test:
score: 0
Extra Test Passed