QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42578 | #3220. Dictionary | _Veritas | AC ✓ | 1077ms | 16252kb | C++ | 2.8kb | 2022-08-02 18:18:36 | 2022-08-02 18:18:38 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(x) (int) x.size()
#define rep(i,a,b) for (int i = a;i < b;i++)
using ll = long long;
template<typename T> using V = std::vector<T>;
template<typename X,typename Y> bool ckmin(X& x,const Y& y) { return (y < x) ? (x = y,1) : 0;}
template<typename X,typename Y> bool ckmax(X& x,const Y& y) { return (y > x) ? (x = y,1) : 0;}
using std::cin;
using std::cout;
using std::cerr;
constexpr ll MOD = 1e9 + 7;
ll qm(ll x) {
return x >= MOD ? x - MOD : x;
}
void add(ll& x,ll y) {
x += y;
if (x >= MOD) x -= MOD;
}
ll qpow(ll b,ll p) {
ll ret = 1;
while (p != 0) {
if (p & 1) ret = ret * b % MOD;
p >>= 1, b = b * b % MOD;
}
return ret;
}
ll inv(ll x) {
return qpow(x, MOD - 2);
}
int n;
char s[50][23];
int count(char* s) {
int cnt = 0;
while (*s != '\0') {
if (*s == '?')cnt++;
s++;
}
return cnt;
}
int toInt(char c) {
return c == '\0' ? 0 : c - 'a' + 1;
}
ll dp[22][51][51][28];
ll rec(int k,int l,int r,int f) {
ll& ret = dp[k][l][r][f];
if (ret != -1) return ret;
if (s[l][k] != '?' && toInt(s[l][k]) != f) return ret = 0;
if (s[l][k] == '?' && f == 0) return ret = 0;
if (l == r) {
ret = qpow(26,count(s[l] + k + 1));
} else {
for (int j = l + 1;j <= r;j++) {
if (s[j][k] == 0) return ret = 0;
}
ll ans = 0;
bool t = 1;
for (int j = l + 1;j <= r;j++) {
if (s[j][k] == '?') {
ll vl = 0,vr = 0;
for (int jj = f + 1;jj < 27;jj++) {
add(vr,rec(k,j,r,jj));
}
for (int ff = 0;ff < 27;ff++) {
add(vl,rec(k + 1,l,j - 1,ff));
}
add(ans,vl * vr % MOD);
} else if (toInt(s[j][k]) > f) {
for (int ff = 0;ff < 27;ff++) {
add(ans,rec(k + 1,l,j - 1,ff) * rec(k,j,r,toInt(s[j][k])) % MOD);
}
}
if ((s[j][k] != '?' && toInt(s[j][k]) != f) || (f == 0 && s[j][k] == '?')) {
t = 0;
break;
}
}
if (t) {
for (int i = 0;i < 27;i++) {
add(ans,rec(k + 1,l,r,i));
}
}
ret = ans;
}
return ret;
}
void solve() {
memset(dp,-1,sizeof(dp));
cin>>n;
for (int i = 0;i < n;i++) {
cin>>s[i];
}
ll ans = 0;
for (int i = 1;i < 27;i++) {
add(ans,rec(0,0,n - 1,i));
}
cout<<ans<<'\n';
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cin.exceptions(cin.failbit);
#ifdef DEBUG
freopen("input.txt","r",stdin);
#endif
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 16100kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 3ms
memory: 16252kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1077ms
memory: 16056kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
346258309
result:
ok single line: '346258309'
Test #4:
score: 0
Accepted
time: 2ms
memory: 16048kb
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: 16184kb
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: 0ms
memory: 16152kb
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: 2ms
memory: 16120kb
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: 16124kb
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: 0ms
memory: 16180kb
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: 16124kb
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: 5ms
memory: 16252kb
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: 16184kb
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: 7ms
memory: 16168kb
input:
9 ???r?????????v?? ????????????? ??????q?????? ???????q?????????? ?? ?????????????????? ???? ?????????? ????v
output:
832577674
result:
ok single line: '832577674'
Test #14:
score: 0
Accepted
time: 7ms
memory: 16112kb
input:
8 ???????????????????? ????? ???????????? ??????????????????? ????? ????????????????? ????? ????????????
output:
823652145
result:
ok single line: '823652145'
Test #15:
score: 0
Accepted
time: 2ms
memory: 16120kb
input:
2 ?sum??mer c??a??mp
output:
703286064
result:
ok single line: '703286064'
Test #16:
score: 0
Accepted
time: 6ms
memory: 16252kb
input:
3 snuje ????e snule
output:
1
result:
ok single line: '1'