Submission #60033005

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

#define ll long long
#define rep(i,r) for(ll i=0;(int)(i)<(int)(r);i++)
#define mint static_modint<mod>
#define vm(n,i) vector<mint>(n,i)
#define v2m(n,m,i) vector<vector<mint>>(n,vm(m,i))
#define v3m(n,m,k,i) vector<vector<vector<mint>>>(n,v2m(m,k,i))
#define v4m(n,m,k,l,i) vector<vector<vector<vector<mint>>>>(n,v3m(m,k,l,i))
#define v5m(n,m,k,l,o,i) vector<vector<vector<vector<vector<mint>>>>>(n,v4m(m,k,l,o,i))
#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)

const ll mod = 998244353;

tuple<ll,ll,ll,ll> next_state(ll x,ll a,ll b,ll c,ll n){
    x ^= n;
    if(x==1) a++;
    else if(x==2) b++;
    else if(x==3) c++;
    return make_tuple(x,a,b,c);
}

int main(){
    riano_; mint ans = 0;
    ll N,K; cin >> N >> K;
    string S; cin >> S;

    auto dp = v5m(N+1,4,N+2,N+2,N+2,0); dp[0][0][0][0][0] = 1;
    rep(i,N){
        rep(x,4){
            rep(a,N+1){
                rep(b,N+1){
                    rep(c,N+1){
                        rep(n,3){
                            if(S[i]=='A'+n||S[i]=='?'){
                                auto[nx,na,nb,nc] = next_state(x,a,b,c,n+1);
                                dp[i+1][nx][na][nb][nc] += dp[i][x][a][b][c];
                            }
                        }
                    }
                }
            }
        }
    }

    rep(x,4){
        rep(a,N+1){
            rep(b,N+1){
                rep(c,N+1){
                    ll d = (N+1)-(a+b+c);
                    if(a*(a-1)/2+b*(b-1)/2+c*(c-1)/2+d*(d-1)/2>=K){
                        ans += dp[N][x][a][b][c];
                    }
                }
            }
        }
    }

    cout << ans.val() << endl;
}

Submission Info

Judge Result