QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456775 | #3220. Dictionary | propane | WA | 963ms | 12760kb | C++20 | 2.1kb | 2024-06-28 13:17:21 | 2024-06-28 13:17:21 |
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 + 1; 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] = 0;
return f[l][r][st][c] = dp(l + 1, r, st, c);
}
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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12760kb
input:
2 b? a??
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 3ms
memory: 12660kb
input:
1 snuke
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 963ms
memory: 12652kb
input:
50 ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???????????????????? ???...
output:
116161576
result:
wrong answer 1st lines differ - expected: '346258309', found: '116161576'