QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795528#9536. Athlete Welcome CeremonyPepinotWA 177ms236488kbC++233.2kb2024-11-30 21:12:092024-11-30 21:12:09

Judging History

This is the latest submission verdict.

  • [2024-11-30 21:12:09]
  • Judged
  • Verdict: WA
  • Time: 177ms
  • Memory: 236488kb
  • [2024-11-30 21:12:09]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vii vector<pair<int, int>>
#define ff first
#define ss second
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =

int dp[310][310][310][3]; // ijkz  对前i个字符,使用了j个a字符,k个b字符,第i个字符是 z + 'a'的方案数
int f[310][310][310]; // 有i个a,j个b,k个c的方案数

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = ' ' + s;
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + (s[i] == '?');

    // 先初始化一下方案数
    if (s[1] == '?')
        dp[1][1][0][0] = dp[1][0][1][1] = dp[1][0][0][2] = 1;
    else
        dp[1][0][0][s[1] - 'a'] = 1;


    for (int i = 2; i <= n; i++) {
        for (int ca = 0; ca <= cnt[i]; ca++) {
            for (int cb = 0; cb + ca <= cnt[i]; cb++) {
                if (s[i] != '?') {
                    int num = dp[i - 1][ca][cb][0] + dp[i - 1][ca][cb][1] + dp[i - 1][ca][cb][2]; //上一层总方案数
                    dp[i][ca][cb][s[i] - 'a'] = (num - dp[i - 1][ca][cb][s[i] - 'a']) % mod; // 去掉上一层一样的,其他结尾字母为0
                    continue;
                }
                if (ca) {
                    int num = dp[i - 1][ca - 1][cb][1] + dp[i - 1][ca - 1][cb][2];
                    dp[i][ca][cb][0] = num % mod;
                }
                if (cb) {
                    int num = dp[i - 1][ca][cb - 1][0] + dp[i - 1][ca][cb - 1][2];
                    dp[i][ca][cb][1] = num % mod;
                }
                if (cnt[i] - ca - cb) {
                    int num = dp[i - 1][ca][cb][0] + dp[i - 1][ca][cb][1];
                    dp[i][ca][cb][2] = num % mod;
                }
            }
        }
    }

    // 先获得特定i j k对应的方案数
    for (int i = 0; i <= cnt[n]; i++)
        for (int j = 0; i + j <= cnt[n]; j++) {
            int num = dp[n][i][j][0] + dp[n][i][j][1] + dp[n][i][j][2];
            f[i][j][cnt[n] - i - j] = num % mod;
        }


    //----------------From there

    // 获得i j k有富余的情况对应的方案数 三维前缀和
    for (int i = 0; i <= 300; i++) {
        for (int j = 0; j <= 300; j++) {
            for (int k = 0; k <= 300; k++) {
                if (i) f[i][j][k] += f[i - 1][j][k];
                if (j) f[i][j][k] += f[i][j - 1][k];
                if (k) f[i][j][k] += f[i][j][k - 1];
                if (i && j) f[i][j][k] +=  f[i - 1][j - 1][k];
                if (k && j) f[i][j][k] +=  f[i][j - 1][k - 1];
                if (i && k) f[i][j][k] +=  f[i - 1][j][k - 1];
                if (i && j && k) f[i][j][k] += f[i - 1][j - 1][k - 1];
                f[i][j][k] %= mod;
            }
        }
    }

    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        cout << f[x][y][z] << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 177ms
memory: 236488kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

23
1
1

result:

wrong answer 1st lines differ - expected: '3', found: '23'