QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456774#3220. DictionarypropaneWA 1001ms12840kbC++201.9kb2024-06-28 13:14:392024-06-28 13:14:39

Judging History

你现在查看的是最新测评结果

  • [2024-06-28 13:14:39]
  • 评测
  • 测评结果:WA
  • 用时:1001ms
  • 内存:12840kb
  • [2024-06-28 13:14:39]
  • 提交

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'