QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799103#3220. DictionaryInvincibleAC ✓98ms75636kbC++231.9kb2024-12-04 22:08:242024-12-04 22:08:25

Judging History

This is the latest submission verdict.

  • [2024-12-04 22:08:25]
  • Judged
  • Verdict: AC
  • Time: 98ms
  • Memory: 75636kb
  • [2024-12-04 22:08:24]
  • Submitted

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'