QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189940 | #3220. Dictionary | KKT89 | AC ✓ | 84ms | 10672kb | C++17 | 2.5kb | 2023-09-28 01:39:55 | 2023-09-28 01:39:56 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <array>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
constexpr ll mod = 1e9+7;
string s[51];
int dp[51][51][22][27];
bool done[51][51][22][27];
void add(int &x, int y){
x += y;
if(x >= mod)x -= mod;
}
int mul(int x, int y){
return 1LL*x*y%mod;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n; cin >> n;
for(int i=0;i<n;i++){
cin >> s[i];
}
auto solve=[&](auto self,int l,int r,int idx,int c)->int{
if(l == r) return 1;
// メモ化
if(done[l][r][idx][c]) return dp[l][r][idx][c];
done[l][r][idx][c] = true;
// これ以上文字は使えないよ
if(c >= 26){
dp[l][r][idx][c] = 0;
return 0;
}
// 文字列長のチェック
for(int j=l;j<r;j++){
if(l<j and (int)s[j].size() == idx){
dp[l][r][idx][c] = 0; return 0;
}
if((int)s[j].size() < idx){
dp[l][r][idx][c] = 0; return 0;
}
}
// lを一つズラす
// (上の1つ目のif文で i<j⇨s_{i}<s_{j} が違反されることはない)
if((int)s[l].size() == idx){
int res = self(self,l+1,r,idx,c);
dp[l][r][idx][c] = res;
return res;
}
// s[l][idx]がc+1の時
int res = self(self,l,r,idx,c+1);
// s[l][idx]がcの時
for(int j=l;j<r;j++){
if(s[j][idx] != (char)('a'+c) and s[j][idx] != '?')break;
add(res, mul(self(self,l,j+1,idx+1,0), self(self,j+1,r,idx,c+1)));
}
dp[l][r][idx][c] = res;
return res;
};
cout << solve(solve,0,n,0,0) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5664kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 84ms
memory: 10672kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
346258309
result:
ok single line: '346258309'
Test #4:
score: 0
Accepted
time: 0ms
memory: 8108kb
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: 0ms
memory: 7940kb
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: 10016kb
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: 5916kb
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: 5848kb
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: 1ms
memory: 10116kb
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: 8112kb
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: 1ms
memory: 8016kb
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: 8024kb
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: 5832kb
input:
9 ???r?????????v?? ????????????? ??????q?????? ???????q?????????? ?? ?????????????????? ???? ?????????? ????v
output:
832577674
result:
ok single line: '832577674'
Test #14:
score: 0
Accepted
time: 0ms
memory: 5848kb
input:
8 ???????????????????? ????? ???????????? ??????????????????? ????? ????????????????? ????? ????????????
output:
823652145
result:
ok single line: '823652145'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
2 ?sum??mer c??a??mp
output:
703286064
result:
ok single line: '703286064'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
3 snuje ????e snule
output:
1
result:
ok single line: '1'