QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42565#3220. DictionaryafhiAC ✓1099ms16252kbC++2.8kb2022-08-02 18:02:522022-08-02 18:02:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-02 18:02:54]
  • 评测
  • 测评结果:AC
  • 用时:1099ms
  • 内存:16252kb
  • [2022-08-02 18:02:52]
  • 提交

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: 1ms
memory: 16128kb

input:

2
b?
a??

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 2ms
memory: 16096kb

input:

1
snuke

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1099ms
memory: 16116kb

input:

50
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
???...

output:

346258309

result:

ok single line: '346258309'

Test #4:

score: 0
Accepted
time: 2ms
memory: 16184kb

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: 7ms
memory: 16188kb

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: 7ms
memory: 16124kb

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: 16252kb

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: 3ms
memory: 16180kb

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: 16096kb

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: 4ms
memory: 16152kb

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: 8ms
memory: 16120kb

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: 3ms
memory: 16048kb

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: 16180kb

input:

9
???r?????????v??
?????????????
??????q??????
???????q??????????
??
??????????????????
????
??????????
????v

output:

832577674

result:

ok single line: '832577674'

Test #14:

score: 0
Accepted
time: 8ms
memory: 15984kb

input:

8
????????????????????
?????
????????????
???????????????????
?????
?????????????????
?????
????????????

output:

823652145

result:

ok single line: '823652145'

Test #15:

score: 0
Accepted
time: 2ms
memory: 16048kb

input:

2
?sum??mer
c??a??mp

output:

703286064

result:

ok single line: '703286064'

Test #16:

score: 0
Accepted
time: 0ms
memory: 16120kb

input:

3
snuje
????e
snule

output:

1

result:

ok single line: '1'