QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799103 | #3220. Dictionary | Invincible | AC ✓ | 98ms | 75636kb | C++23 | 1.9kb | 2024-12-04 22:08:24 | 2024-12-04 22:08:25 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){x=max(x,y);}
template<typename T>void chkmin(T&x,const T&y){x=min(x,y);}
const int mod=1e9+7;
int dp[55][55][55][55],n;
string s[55];
int DP(int l,int r,int k,int x){
if(l>r)return 1;
if(x==26)return 0;
if(k==20)return l==r;
if(x==-1){
if(s[l][k]!='?'&&s[l][k]<'a')return DP(l+1,r,k,0);
x=0;
}
if(~dp[l][r][k][x])return dp[l][r][k][x];
int res=0;
rep(i,l,r)if(s[i][k]!='?'&&s[i][k]-'a'<x)return dp[l][r][k][x]=0;
res=DP(l,r,k,x+1);
rep(i,l,r){
if(s[i][k]!='?'&&s[i][k]-'a'!=x)break;
res=(res+DP(l,i,k+1,-1)*DP(i+1,r,k,x+1))%mod;
}
return dp[l][r][k][x]=res;
}
signed main(){
n=read();
rep(i,1,n)cin>>s[i];
rep(i,1,n)while(s[i].size()<20)s[i]=s[i]+char('a'-1);
memset(dp,-1,sizeof dp);
printf("%lld\n",DP(1,n,0,-1));
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 75340kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 75304kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 98ms
memory: 75236kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
346258309
result:
ok single line: '346258309'
Test #4:
score: 0
Accepted
time: 3ms
memory: 75272kb
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: 75300kb
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: 3ms
memory: 75276kb
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: 9ms
memory: 75532kb
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: 0ms
memory: 75272kb
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: 75632kb
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: 75636kb
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: 0ms
memory: 75320kb
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: 75272kb
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: 5ms
memory: 75340kb
input:
9 ???r?????????v?? ????????????? ??????q?????? ???????q?????????? ?? ?????????????????? ???? ?????????? ????v
output:
832577674
result:
ok single line: '832577674'
Test #14:
score: 0
Accepted
time: 7ms
memory: 75320kb
input:
8 ???????????????????? ????? ???????????? ??????????????????? ????? ????????????????? ????? ????????????
output:
823652145
result:
ok single line: '823652145'
Test #15:
score: 0
Accepted
time: 0ms
memory: 75244kb
input:
2 ?sum??mer c??a??mp
output:
703286064
result:
ok single line: '703286064'
Test #16:
score: 0
Accepted
time: 0ms
memory: 75504kb
input:
3 snuje ????e snule
output:
1
result:
ok single line: '1'