QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117912 | #3220. Dictionary | i_am_noob# | AC ✓ | 27ms | 9236kb | C++14 | 1.3kb | 2023-07-02 14:17:45 | 2023-07-02 14:17:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
const int mod = 1000'000'007, N = 55, K = 22, C = 28;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int mul(int x, int y){return ((ll)x)*y%mod;}
int n,dp[N][N][K+1][C];
string s[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i) cin >> s[i];
for(int i=0; i<n; ++i) while(sz(s[i])<K) s[i]+='a'-1;
for(int l=0; l<=n; ++l) for(int i=0; i+l<=n; ++i) for(int k=K; k>=0; --k) for(int c=0; c<=27; ++c){
int j=i+l;
if(i==j){
dp[i][j][k][c]=1;
continue;
}
dp[i][j][k][c]=0;
if(c==0) continue;
if(k==K){
dp[i][j][k][c]=j==i+1;
continue;
}
dp[i][j][k][c]=dp[i][j][k][c-1];
for(int m=j-1; m>=i; --m){
if(s[m][k]!='?'&&s[m][k]!='a'-1+(c-1)) break;
if(c==1&&s[m][k]=='?') break;
dp[i][j][k][c]=add(dp[i][j][k][c],mul(dp[i][m][k][c-1],dp[m][j][k+1][27]));
}
//if(dp[i][j][k][c]) cout << i << ' ' << j << ' ' << k << ' ' << c << ' ' << dp[i][j][k][c] << endl;
}
cout << dp[0][n][0][27] << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3336kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 27ms
memory: 9236kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
346258309
result:
ok single line: '346258309'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7704kb
input:
25 aaaxklheghvqcyhaaegt ailuhkqqhucpoltg akcfcogzatyskqjy dgdnbelgruel dpj f gabfclzgnumdr gkwhkkfpwarkckan grrkpowoxwggxaknmltj jexnrdunivxqjzfbzso jnq jxpbzggjxb lkpekxxnebfrwi mupwjjjfiwwh ocejbxf pazgt rcftwxjrtgayvllut ryqktm wlyfhhkefuvg xmoluqlzvu xpndemqmtjw ycnsnmwofe ylcvkfealgonjk yn yova...
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 8092kb
input:
24 anseu asdeih b eddm f? g?diquh??ozksxxf hfrqkf ?ithni hmgggszwtkcb js?lw klnwxoi mvqgfgznt nqitd?o??txnsa oauaxbcehlkag ossqwtp qf?uz qhvnsms?nray sniutmg?fjmssf?g sy ukbd ukgqvpvxvmatu?nb xnc??nkrtd?noeblhlx zbagauk?ta?qjfi zbigkdqxkfwtsbvksmf
output:
908807140
result:
ok single line: '908807140'
Test #6:
score: 0
Accepted
time: 1ms
memory: 8208kb
input:
29 ?dh?lmaz?dkavd baalur?h?ioqexoxhe dzxctb?g?c?tmgwjx e elnczxb?z?b?r gysb??ra?rswgrs hci?p??eutsrcwk? hwi?d?i?ffj?gli ic?rg?utvn j j?lyfhq?jga?oxf ?nrlpoz???cabzow jpcln?hljq ?lfvgsja n?uq?lgfvbqdhcnnb pi po???hq?xscyxoutxy? p??q?tj?vdu?zx? qcv qpjamsjeilrling ?l?i??f?j?v?aobxjeh ujzsibul vm??ci?n...
output:
86016979
result:
ok single line: '86016979'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
7 c hge??tc??vnqvyn? ho?xj?u??hl?u pcn?h qa?ua?e?d? v???vnn?nzvonp?z ?ok??ji?swqd??k?rn
output:
636316133
result:
ok single line: '636316133'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
5 dye?c??wpmfoo???je?? iu?qc???k?ydzn m??ko?v t??f?bh??y???k?pu?? ???iz?xo?
output:
662633205
result:
ok single line: '662633205'
Test #9:
score: 0
Accepted
time: 3ms
memory: 7920kb
input:
31 ?jm?mv? c?v?? ????????j?dj epwgqg??eqi? ?? g???a??q?nfcdy h?? i?ljs?f???h?ha jb?? ???????fjnzy??t ?wa??o?gi?huf?? kl?? ltk?igy??z ??e???zz?q?yyxso? ???????tukwt?ao??ke ?l? nv??b? omq onws?h??pp q?g?? ?kna?oybaqu???o?? r?? ??uqoja?g?zn???? ?ca? t?f??z??? ??iws?qyk????o v??g???m??q?y? vq?x?o?w??h?f...
output:
909975318
result:
ok single line: '909975318'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7664kb
input:
26 ?t?????pl???w br???n??tx d?l????bc????????? e ?f?w???? g?gm i?bai?ss???h? is? j?c?? ?iip??a?ft?z??gh k???g l?a?y ???zgjb?e ?h?x ????xo??????x? ?v????????i ???iqm???gio?? ?go?dk?????n????? ??? ?r w?dc?vo?u?p?e???y ???? ?e??brd? z?????ir?stb????lo? ??sg????????? ???b?
output:
841808960
result:
ok single line: '841808960'
Test #11:
score: 0
Accepted
time: 2ms
memory: 5488kb
input:
11 ?????z?s?z?sd???? ???x? h???? ???o???ob?? s?????t ???k?? ???a?yo ve???t??ru ?k??????s??i ?k????????t??c ???o??
output:
60923896
result:
ok single line: '60923896'
Test #12:
score: 0
Accepted
time: 2ms
memory: 5628kb
input:
13 ??? ?????????????? f??? ?ee?x??????? ? ????? ???k??b???????? ????????????? ?t?a? ??t?q?? ????? ????????? ???i????q
output:
902089972
result:
ok single line: '902089972'
Test #13:
score: 0
Accepted
time: 0ms
memory: 5556kb
input:
9 ???r?????????v?? ????????????? ??????q?????? ???????q?????????? ?? ?????????????????? ???? ?????????? ????v
output:
832577674
result:
ok single line: '832577674'
Test #14:
score: 0
Accepted
time: 0ms
memory: 5700kb
input:
8 ???????????????????? ????? ???????????? ??????????????????? ????? ????????????????? ????? ????????????
output:
823652145
result:
ok single line: '823652145'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
2 ?sum??mer c??a??mp
output:
703286064
result:
ok single line: '703286064'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
3 snuje ????e snule
output:
1
result:
ok single line: '1'