#1150651 (C++23) No.3458 Scores of Subsequence

提出ソース
結果

問題	No.3458 Scores of Subsequence
コンテスト
ユーザー	moooaki
提出日時	2026-02-28 16:13:33
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	TLE
実行時間	-
コード長	17,008 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	8,430 ms
コンパイル使用メモリ	408,104 KB
実行使用メモリ	58,484 KB
最終ジャッジ日時	2026-02-28 16:13:51
合計ジャッジ時間	17,698 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 11 TLE * 3 -- * 11
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <atcoder/all>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef DEBUG
#include <icecream.hpp>
#endif
#ifndef DEBUG
#define IC(...) {}
#endif
using namespace atcoder;
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
using mint = modint998244353;

//#define MOD (long long)(1e9+7)
constexpr ll MOD = 998244353LL;
//constexpr ll MOD = (long long)(1e9+7);
constexpr ll INF = (1LL<<60);
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i,n) for(ll i = 1; i <= (ll)(n); i++)
#define rep3(i,s,n) for(ll i = s; i <= (ll)(n); i++)
#define RC(r, c) ((r) * N + (c))
#define R(rc) (rc / N)
#define C(rc) (rc % N)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()


int DR[] = {0, 1, 0, -1};
int DC[] = {1, 0, -1, 0};
char DIREC[] = "RDLU";

int N, M;
int H, W;


using Graph=vector<vector<ll>>;

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

// トライ木 Grokに書いてもらった。
struct Trie {
    struct Node {
        map<char, int> next; // 子ノード（文字→インデックス）
        bool is_end;         // 終端フラグ
        Node() : is_end(false) {}
    };
    vector<Node> nodes;
    
    Trie() { nodes.push_back(Node()); } // 根ノード
    
    void insert(const string& s) {
        int cur = 0;
        for (char c : s) {
            if (nodes[cur].next.find(c) == nodes[cur].next.end()) {
                nodes[cur].next[c] = nodes.size();
                nodes.push_back(Node());
            }
            cur = nodes[cur].next[c];
        }
        nodes[cur].is_end = true;
    }
    
    bool search(const string& s) {
        int cur = 0;
        for (char c : s) {
            if (nodes[cur].next.find(c) == nodes[cur].next.end()) return false;
            cur = nodes[cur].next[c];
        }
        return nodes[cur].is_end;
    }
    
    bool remove(const string& s) {
        int cur = 0;
        for (char c : s) {
            if (nodes[cur].next.find(c) == nodes[cur].next.end()) return false; // 単語が存在しない
            cur = nodes[cur].next[c];
        }
        if (!nodes[cur].is_end) return false; // 単語が終端でない（存在しない）
        nodes[cur].is_end = false; // 終端フラグを外す
        return true;
    }
};


using ll = long long;
using Edge = pair<int, ll>; // to, weight
//const ll INF = (1LL<<62);

void dijkstra(int start, const vector<vector<Edge>> &graph, vector<ll>& dist) {
    int n = graph.size();
    dist.assign(n, INF);
    dist[start] = 0;

    using State = pair<ll, int>; // dist, node
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0LL, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (auto &e : graph[u]) {
            int v = e.first;
            ll w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// 多始点ダイクストラ
void multi_start_dijkstra(const vector<int> &starts,
                          const vector<vector<Edge>> &graph,
                          vector<ll> &dist) {
    int n = graph.size();
    dist.assign(n, INF);

    using State = pair<ll, int>;
    priority_queue<State, vector<State>, greater<State>> pq;

    for (int s : starts) {
        dist[s] = 0;
        pq.push({0LL, s});
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto &e : graph[u]) {
            int v = e.first;
            ll w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

void zero_one_bfs(int start, const vector<vector<Edge>> &graph, vector<ll> &dist) {
    int n = graph.size();
    dist.assign(n, INF);
    dist[start] = 0;

    deque<int> dq;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto &e : graph[u]) {
            int v = e.first;
            ll w = e.second; // 0 or 1
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}

void bfs(int start, const vector<vector<Edge>> &graph, vector<int> &dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &e : graph[u]) {
            int v = e.first;
            if (dist[v] == INT_MAX) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

void warshall_floyd(vector<vector<ll>> &dist) {
    /* 初期化例
       vector<vector<ll>> dist(n, vector<ll>(n, INF));
       for (int i = 0; i < n; i++) dist[i][i] = 0;
       
       for (int u = 0; u < n; u++) {
       for (auto &e : graph[u]) {
       int v = e.first;
       ll w = e.second;
       dist[u][v] = min(dist[u][v], w);
       }
       }
    */

    int n = dist.size();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

bool bellman_ford(int start, const vector<vector<Edge>> &graph, vector<ll> &dist) {
    int n = graph.size();
    dist.assign(n, INF);
    dist[start] = 0;

    for (int iter = 0; iter < n - 1; iter++) {
        bool updated = false;
        for (int u = 0; u < n; u++) {
            if (dist[u] == INF) continue;
            for (auto &e : graph[u]) {
                int v = e.first;
                ll w = e.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
        }
        if (!updated) break;
    }

    // 負閉路検出
    for (int u = 0; u < n; u++) {
        if (dist[u] == INF) continue;
        for (auto &e : graph[u]) {
            int v = e.first;
            ll w = e.second;
            if (dist[u] + w < dist[v]) {
                return false; // negative cycle exists
            }
        }
    }
    return true;
}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// 有理MODを分数に直すやつ
pair<long long, long long> rational_reconstruction(long long x, long long _MOD) {
    long long r0 = _MOD, r1 = x;
    long long s0 = 1, s1 = 0;
    long long t0 = 0, t1 = 1;

    while (r1 * r1 > _MOD) {
        long long q = r0 / r1;
        tie(r0, r1) = make_pair(r1, r0 - q * r1);
        tie(s0, s1) = make_pair(s1, s0 - q * s1);
        tie(t0, t1) = make_pair(t1, t0 - q * t1);
    }
    return {r1, t1}; // r1 / t1
}

#define MAX 1000000

std::vector<long long> fact(MAX + 1), inv_fact(MAX + 1);

// モジュロMODでx^yを計算する（繰り返し二乗法）
long long mod_pow(long long x, long long y, int mod) {
    long long res = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
        y /= 2;
    }
    return res;
}

// 階乗と階乗の逆元を事前に計算しておく
// comb()呼び出し前に呼ぶ
void init_comb() {
    fact[0] = 1;
    for (int i = 1; i <= MAX; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[MAX] = mod_pow(fact[MAX], MOD - 2, MOD);  // フェルマーの小定理を使用して逆元を計算
    for (int i = MAX - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

// 二項係数 nCk を計算する
// init_comb() 
long long comb(int n, int k) {
    if (n < k || k < 0) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// 最大公約数 std::gcl()があるよ
ll gcd(ll a, ll b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

// mod m におけるa の逆元 // ACL使えばよさげ
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 素因数分解 // おそい
vector<pair<ll, ll>> pf0(ll n) {
    vector<pair<ll, ll>> res;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            res.push_back({i, cnt});
        }
    }
    if (n > 1) res.push_back({n, 1});
    return res;
}

bool inside(int r, int c)
{
    return r >= 0 && r < N && c >= 0 && c < N;
}

inline bool inside(int r, int c, int h, int w)
{
    return r >= 0 && r < h && c >= 0 && c < w;
}

template <class T>
class Grid
{
public:
    int H, W;
    int HW;
    vector<T> grid;

    Grid() {}

    Grid(int n) {
        H = W = n;
        HW = H * W;
        grid.resize(HW, T(0));
    }

    Grid(int h, int w) {
        H = h;
        W = w;
        HW = H * W;
        grid.resize(HW, T(0));
    }

    void fill(const T& v) {
        std::fill(grid.begin(), grid.end(), v);
    }

    void read() {
        for(int r = 0; r < H; r++) {
            for(int c = 0; c < W; c++) {
                cin >> at(r, c);
            }
        }
    }

    inline bool inside(int r, int c) const {
        return (r >= 0 && r < H && c >= 0 && c < W);
    }

    T& operator()(int r, int c) {
        return grid[r * W + c];
    }

    const T& operator()(int r, int c) const {
        return grid[r * W + c];
    }

    T& at(int rc) {
        assert(0 <= rc && rc < HW);
        return grid[rc];
    }

    const T& at(int rc) const {
        assert(0 <= rc && rc < HW);
        return grid[rc];
    }

    T& at(int r, int c) {
        assert(inside(r, c));
        return grid[r * W + c];
    }

    const T& at(int r, int c) const {
        assert(inside(r, c));
        return grid[r * W + c];
    }

    void show() const {
        for(int r = 0; r < H; r++) {
            for(int c = 0; c < W; c++) {
                cerr << at(r, c);
            }
            cerr << '\n';
        }
    }

    void show2() const {
        for(int r = 0; r < H; r++) {
            for(int c = 0; c < W; c++) {
                cerr << setw(3) << at(r, c);
            }
            cerr << '\n';
        }
    }
};



// エラトステネスの篩
vector<char> sieve_char(int n) {
    vector<char> isp(n + 1, 1);
    isp[0] = isp[1] = 0;
    for (int i = 2; i * i <= n; i++) {
        if (isp[i]) {
            for (long long j = 1LL * i * i; j <= n; j += i) {
                isp[j] = 0;
            }
        }
    }
    return isp;
}


// 転倒数
// b は 0 〜 (b.size()-1) の範囲に座圧済みの値
ll inversion(vector<ll> b) {
    ll ans = 0;
    fenwick_tree<ll> fw(b.size());
    rep(j, (ll)b.size()) {
        ans += j - fw.sum(0, b[j]);
        fw.add(b[j], 1);
    }
    return ans;
}

// ランレングス
template <class T>
vector<pair<T,long long>> run_length(const vector<T>& a) {
    vector<pair<T,long long>> res;
    if (a.empty()) return res;

    T cur = a[0];
    long long cnt = 1;

    for (size_t i = 1; i < a.size(); i++) {
        if (a[i] == cur) {
            cnt++;
        } else {
            res.emplace_back(cur, cnt);
            cur = a[i];
            cnt = 1;
        }
    }
    res.emplace_back(cur, cnt);
    return res;
}

// 座標圧縮
template<class T>
vector<T> compress(vector<T> v) {
    vector<T> xs = v;
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (auto &e : v) {
        e = lower_bound(xs.begin(), xs.end(), e) - xs.begin();
    }
    return xs;
}


// -----------------------------------------
// 桁DPテンプレ：count[0..N] に対して何か数える
// -----------------------------------------
#include <bits/stdc++.h>
using namespace std;

string S;       // N
int L;          // 桁数

// DP の状態：pos, tight, ...（必要なら外側で変数追加）
long long dp[105][2];  // 例：状態が小さい場合（配列の次元は後で増やす）
bool used[105][2];

// 必要に応じて状態を構造体にしてもOK
long long dfs(int pos, bool tight /*, 他の状態*/) {
    if (pos == L) {
        // 「末尾に到達したときのcount条件」はここで判定
        return 1;   // 条件を満たすなら1, そうでなければ0
    }

    if (!tight && used[pos][0]) return dp[pos][0];

    int limit = tight ? (S[pos]-'0') : 9;
    long long res = 0;

    for (int d = 0; d <= limit; d++) {
        bool ntight = tight && (d == limit);

        // もし「非0カウント」など他の状態があればここで次状態を計算

        res += dfs(pos+1, ntight /*, next_state*/);
    }

    if (!tight) {
        used[pos][0] = true;
        dp[pos][0] = res;
    }
    return res;
}

int main_dp(){
    cin >> S;
    L = S.size();

    cout << dfs(0, true /*, 初期状態 */) << endl;
    return 0;
}

// 基本のordered_set（重複なし）
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// 重複ありのordered_multiset（おすすめのpair版！安定＆安全）
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

/*
// 使い方例（重複ありの場合）
ordered_multiset s;

// 挿入（重複OK）
s.insert({A[i], timer++});

// 削除（特定の値を1個削除）
auto it = s.lower_bound({val, 0});
if (it != s.end() && it->first == val) s.erase(it);

// k番目（0-based）の値を取る
long long sum = 0;
for (int j = 0; j < K; j++) {
    auto it = s.find_by_order(j);
    if (it != s.end()) sum += it->first;
}
*/

// トポロジカルソート
void topo_sort()
{
    vector<vector<int>> g(N);
    vector<int> indeg(N, 0);

    // 辺の入力
    for(int i = 0; i < M; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        indeg[y]++;
    }

    // dp[v] = vに到達する最長パス長
    vector<int> dp(N, 0);

    queue<int> q;
    for(int i = 0; i < N; i++){
        if(indeg[i] == 0) q.push(i);
    }

    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
            dp[to] = max(dp[to], dp[v] + 1);
            indeg[to]--;
            if(indeg[to] == 0){
                q.push(to);
            }
        }
    }

    // 答え
    int ans = 0;
    for(int i = 0; i < N; i++){
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

// 偏角ソート関連
struct Vec {
    long long x, y;
};
// 半平面判定
inline bool upper(const Vec& a) {
    return (a.y > 0) || (a.y == 0 && a.x > 0);
}
// 外積
inline long long cross(const Vec& a, const Vec& b) {
    return a.x * b.y - a.y * b.x;
}
// 偏角比較（右方向→反時計回り）
bool angle_less(const Vec& a, const Vec& b) {
    bool ua = upper(a);
    bool ub = upper(b);
    if (ua != ub) return ua > ub;
    return cross(a, b) > 0;
}
// 同一直線（同偏角）?
bool same_dir(const Vec& a, const Vec& b) {
    return cross(a, b) == 0 && (a.x * b.x + a.y * b.y) > 0;
}

const int MAXA = 1e7;
vector<int> spf(MAXA + 1);

// pfよぶ前によぶ
void init_spf() {
    for (int i = 1; i <= MAXA; i++) spf[i] = i;
    for (int i = 2; i * i <= MAXA; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j <= MAXA; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

vector<pair<ll,ll>> pf(ll n) {
    vector<pair<ll,ll>> res;
    while (n > 1) {
        ll p = spf[n], cnt = 0;
        while (spf[n] == p) {
            n /= p;
            cnt++;
        }
        res.push_back({p, cnt});
    }
    return res;
}



vector<mint> fac;
vector<mint> invfac;

inline mint nCk(ll n, ll k) {
    return fac[n] * invfac[k] * invfac[n - k];
}

void solve()
{
    mint ans = 0;
    string s; cin >> s;
    ll N = s.size();
    ll mc = 0;
    fac.resize(N + 1);fac[0] = 1;
    invfac.resize(N + 1);invfac[0] = 1 / fac[0];
    rep1(i, N) {
        fac[i] = fac[i - 1] * i;
        invfac[i] = 1 / fac[i];
        IC(fac[i].val(), invfac[i].val());
    }
    rep(i, N) {
        switch(s[i]) {
        case 'M':
            mc ++;
            break;
        case 'A':
            rep(j, mc + 1) {
                ans += mint(2).pow(j) * nCk(mc, j);
            }
            break;
        }
    }
    cout << ans.val() << endl;

}


int main(void)
{
    // ll t; cin >> t; rep(i, t)
    solve();
}
yukicoder

結果

ソースコード
