QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456798 | #3220. Dictionary | propane | AC ✓ | 969ms | 13780kb | C++20 | 2.3kb | 2024-06-28 13:46:48 | 2024-06-28 13:46:48 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
char s[55][30];
int f[55][55][30][28];
int dp(int l, int r, int st, int c){
if (~f[l][r][st][c]) return f[l][r][st][c];
if (l > r) return 1;
if (c > 26) return 0;
if (l == r){
if (s[r][st] == 0) return c == 0;
if (s[r][st] != '?' and s[r][st] < c + 'a' - 1) return 0;
int ans = 1;
if (s[r][st] == '?') ans = min(26, 26 - c + 1);
for(int i = st + 1; i < 20; i++){
if (s[r][i] == '?'){
ans = mul(ans, 26);
}
}
return f[l][r][st][c] = ans;
}
if (st >= 20) return 0;
for(int i = l + 1; i <= r; i++){
if (s[i][st] == 0){
return f[l][r][st][c] = 0;
}
}
if (s[l][st] == 0){
if (c != 0) return f[l][r][st][c] = 0;
return f[l][r][st][c] = dp(l + 1, r, st, c);
}
int ans = 0;
int state = 0;
for(int i = l; i <= r; i++){
if (s[i][st] != '?'){
state |= 1 << (s[i][st] - 'a' + 1);
}
if (__builtin_popcount(state) > 1) break;
int s = 0;
for(int j = max(c, 1); j <= 26; j++){
if (state == 0 or (state >> j & 1)){
add(ans, mul(dp(l, i, st + 1, 0), dp(i + 1, r, st, j + 1)));
s += 26 - j;
}
}
}
// cout << l << ' ' << r << ' ' << st << ' ' << c << ' ' << ans << '\n';
return f[l][r][st][c] = ans;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s[i];
}
memset(f, -1, sizeof f);
cout << dp(1, n, 0, 0) << '\n';
// for(int i = 0; i < 26; i++){
// int cnt = 0;
// for(int j = i + 1; j < 26; j++){
// for(int k = j; k < 26; k++){
// cnt += 1;
// }
// }
// cout << cnt * 26 << '\n';
// }
// cout << cnt * 26 << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 13744kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 13704kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 969ms
memory: 13428kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
346258309
result:
ok single line: '346258309'
Test #4:
score: 0
Accepted
time: 0ms
memory: 13780kb
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: 2ms
memory: 13536kb
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: 2ms
memory: 13708kb
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: 0ms
memory: 13532kb
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: 2ms
memory: 13548kb
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: 2ms
memory: 13708kb
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: 0ms
memory: 13572kb
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: 13476kb
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: 0ms
memory: 13472kb
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: 3ms
memory: 13480kb
input:
9 ???r?????????v?? ????????????? ??????q?????? ???????q?????????? ?? ?????????????????? ???? ?????????? ????v
output:
832577674
result:
ok single line: '832577674'
Test #14:
score: 0
Accepted
time: 0ms
memory: 13424kb
input:
8 ???????????????????? ????? ???????????? ??????????????????? ????? ????????????????? ????? ????????????
output:
823652145
result:
ok single line: '823652145'
Test #15:
score: 0
Accepted
time: 0ms
memory: 13476kb
input:
2 ?sum??mer c??a??mp
output:
703286064
result:
ok single line: '703286064'
Test #16:
score: 0
Accepted
time: 2ms
memory: 13580kb
input:
3 snuje ????e snule
output:
1
result:
ok single line: '1'