Submission #60498636

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int cnt[8];
int dp[55][55][55][55][4];
int n, k;
string s;
const int MOD = (119 << 23) + 1;
int fnCnt(int cnt) {return cnt * (cnt - 1) / 2;}
int transform(int val, char c) {
    return val ^ (1 << (c - 'A'));
}
int solve(int index, int cur) {
    if (cur &  1) cur ^= 7;
    cnt[cur] += 1;
    int &ret = dp[cnt[0]][cnt[2]][cnt[6]][cnt[4]][cur/2];
    if (ret == -1) {
        if (index == n) {
            ret = (fnCnt(cnt[0]) + fnCnt(cnt[2]) + fnCnt(cnt[4]) + fnCnt(cnt[6]) >= k);
        }   else {
            ret = 0;
            for (char c = 'A';c <= 'C';c++) {
                if (s[index] == c|| s[index] == '?') {
                    ret = (ret + solve(index + 1, transform(cur, c))) % MOD;
                }
            }
        }
    }
    cnt[cur] -= 1;
    return ret;
}

void doWork() {

    cin >> n >> k >> s;
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << endl;

}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        doWork();
    }
}

Submission Info

Submission Time
Task A - ABC Symmetry
User triplem5ds
Language C++ 20 (gcc 12.2)
Score 500
Code Size 1082 Byte
Status AC
Exec Time 70 ms
Memory 146560 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 26
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
in-01.txt AC 56 ms 146356 KiB
in-02.txt AC 55 ms 146364 KiB
in-03.txt AC 56 ms 146372 KiB
in-04.txt AC 56 ms 146476 KiB
in-05.txt AC 67 ms 146416 KiB
in-06.txt AC 67 ms 146368 KiB
in-07.txt AC 59 ms 146344 KiB
in-08.txt AC 62 ms 146560 KiB
in-09.txt AC 61 ms 146376 KiB
in-10.txt AC 64 ms 146432 KiB
in-11.txt AC 66 ms 146376 KiB
in-12.txt AC 62 ms 146308 KiB
in-13.txt AC 65 ms 146556 KiB
in-14.txt AC 65 ms 146380 KiB
in-15.txt AC 64 ms 146368 KiB
in-16.txt AC 70 ms 146340 KiB
in-17.txt AC 60 ms 146240 KiB
in-18.txt AC 59 ms 146400 KiB
in-19.txt AC 67 ms 146476 KiB
in-20.txt AC 56 ms 146384 KiB
in-21.txt AC 56 ms 146404 KiB
in-22.txt AC 56 ms 146392 KiB
in-23.txt AC 56 ms 146240 KiB
sample-01.txt AC 57 ms 146340 KiB
sample-02.txt AC 70 ms 146408 KiB
sample-03.txt AC 56 ms 146404 KiB