QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456774 | #3220. Dictionary | propane | WA | 1001ms | 12840kb | C++20 | 1.9kb | 2024-06-28 13:14:39 | 2024-06-28 13:14:39 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
char s[55][30];
int f[55][55][30][26];
int dp(int l, int r, int st, int c){
if (~f[l][r][st][c]) return f[l][r][st][c];
if (l > r) return 1;
if (c > 26) return 0;
if (l == r){
if (s[r][st] == 0) return c == 0;
if (s[r][st] != '?' and s[r][st] < c + 'a' - 1) return 0;
int ans = 1;
if (s[r][st] == '?') ans = 26 - c + 1;
for(int i = st + 1; i < 20; i++){
if (s[r][i] == '?'){
ans = mul(ans, 26);
}
}
return f[l][r][st][c] = ans;
}
if (st >= 20) return 0;
for(int i = l; i <= r; i++){
if (s[i][st] == 0){
return f[l][r][st][c] = 0;
}
}
if (s[l][st] == 0){
if (c == 0) return f[l][r][st][c] = dp(l + 1, r, st, c);
return 0;
}
int ans = 0;
int state = 0;
for(int i = l; i <= r; i++){
if (s[i][st] != '?'){
state |= 1 << (s[i][st] - 'a' + 1);
}
if (__builtin_popcount(state) > 1) break;
for(int j = max(c, 1); j <= 26; j++){
if (state == 0 or (state >> j & 1)){
add(ans, mul(dp(l, i, st + 1, 0), dp(i + 1, r, st, j + 1)));
}
}
}
// cout << l << ' ' << r << ' ' << st << ' ' << c << ' ' << ans << '\n';
return f[l][r][st][c] = ans;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s[i];
}
memset(f, -1, sizeof f);
cout << dp(1, n, 0, 0) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12772kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 2ms
memory: 12836kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 1001ms
memory: 12840kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
116161576
result:
wrong answer 1st lines differ - expected: '346258309', found: '116161576'