#1116452 (C++17) No.3439 [Cherry 8th Tune] どの頂点にいた頃に戻りたいのか?

提出ソース
結果

問題	No.3439 [Cherry 8th Tune] どの頂点にいた頃に戻りたいのか?
コンテスト
ユーザー	👑 Kazun
提出日時	2025-09-01 01:02:46
言語	C++17 (gcc 15.2.0 + boost 1.89.0)
結果	WA
実行時間	-
コード長	8,755 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	2,967 ms
コンパイル使用メモリ	298,120 KB
実行使用メモリ	161,308 KB
最終ジャッジ日時	2026-01-23 20:55:37
合計ジャッジ時間	19,446 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	WA * 1 RE * 1
other	RE * 37
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 2 "/home/user/competitive_programming/library_for_cpp/template/template.hpp"

using namespace std;

// intrinstic
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// utility
#line 2 "/home/user/competitive_programming/library_for_cpp/template/utility.hpp"

using ll = long long;

// a ← max(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmax(T &a, const U b){
    return (a < b ? a = b, 1: 0);
}

// a ← min(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmin(T &a, const U b){
    return (a > b ? a = b, 1: 0);
}
#line 59 "/home/user/competitive_programming/library_for_cpp/template/template.hpp"

// math
#line 2 "/home/user/competitive_programming/library_for_cpp/template/math.hpp"

// 除算に関する関数

// floor(x / y) を求める.
template<typename T, typename U>
T div_floor(T x, U y){ return (x > 0 ? x / y: (x - y + 1) / y); }

// ceil(x / y) を求める.
template<typename T, typename U>
T div_ceil(T x, U y){ return (x > 0 ? (x + y - 1) / y: x / y) ;}

// x を y で割った余りを求める.
template<typename T, typename U>
T mod(T x, U y){
    T q = div_floor(x, y);
    return x - q * y ;
}

// x を y で割った商と余りを求める.
template<typename T, typename U>
pair<T, T> divmod(T x, U y){
    T q = div_floor(x, y);
    return {q, x - q * y};
}

// 四捨五入を求める.
template<typename T, typename U>
T round(T x, U y){
    T q, r;
    tie (q, r) = divmod(x, y);
    return (r >= div_ceil(y, 2)) ? q + 1 : q;
}

// 指数に関する関数

// x の y 乗を求める.
ll intpow(ll x, ll y){
    ll a = 1;
    while (y){
        if (y & 1) { a *= x; }
        x *= x;
        y >>= 1;
    }
    return a;
}

// x の y 乗を z で割った余りを求める.
ll modpow(ll x, ll y, ll z){
    ll a = 1;
    while (y){
        if (y & 1) { (a *= x) %= z; }
        (x *= x) %= z;
        y >>= 1;
    }
    return a;
}

// vector の要素の総和を求める.
ll sum(vector<ll> &X){
    ll y = 0;
    for (auto &&x: X) { y+=x; }
    return y;
}

// vector の要素の総和を求める.
template<typename T>
T sum(vector<T> &X){
    T y = T(0);
    for (auto &&x: X) { y += x; }
    return y;
}
#line 62 "/home/user/competitive_programming/library_for_cpp/template/template.hpp"

// inout
#line 1 "/home/user/competitive_programming/library_for_cpp/template/inout.hpp"
// 入出力
template<class... T>
void input(T&... a){ (cin >> ... >> a); }

void print(){ cout << "\n"; }

template<class T, class... Ts>
void print(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << " ", b));
    cout << "\n";
}

template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &P){
    is >> P.first >> P.second;
    return is;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &P){
    os << P.first << " " << P.second;
    return os;
}

template<typename T>
vector<T> vector_input(int N, int index){
    vector<T> X(N+index);
    for (int i=index; i<index+N; i++) cin >> X[i];
    return X;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &X){
    for (auto &x: X) { is >> x; }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &X){
    int s = (int)X.size();
    for (int i = 0; i < s; i++) { os << (i ? " " : "") << X[i]; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &S){
    int i = 0;
    for (T a: S) {os << (i ? " ": "") << a; i++;}
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}
#line 65 "/home/user/competitive_programming/library_for_cpp/template/template.hpp"

// macro
#line 2 "/home/user/competitive_programming/library_for_cpp/template/macro.hpp"

// マクロの定義
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define unless(cond) if (!(cond))

// オーバーロードマクロ
#define overload2(_1, _2, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name

// 繰り返し系
#define rep1(n) for (ll i = 0; i < n; i++)
#define rep2(i, n) for (ll i = 0; i < n; i++)
#define rep3(i, a, b) for (ll i = a; i < b; i++)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define foreach1(x, a) for (auto &&x: a)
#define foreach2(x, y, a) for (auto &&[x, y]: a)
#define foreach3(x, y, z, a) for (auto &&[x, y, z]: a)
#define foreach4(x, y, z, w, a) for (auto &&[x, y, z, w]: a)
#define foreach(...) overload5(__VA_ARGS__, foreach4, foreach3, foreach2, foreach1)(__VA_ARGS__)
#line 2 "/home/user/competitive_programming/library_for_cpp/modint.hpp"

template<int mod>
class modint{
    public:
    int64_t x;

    public:
    // 初期化
    constexpr modint(): x(0) {}
    constexpr modint(int64_t a): x((a % mod + mod) % mod) {}

    // マイナス元
    modint operator-() const { return modint(-x); }

    // 加法
    modint& operator+=(const modint &b){
        if ((x += b.x) >= mod) x -= mod;
        return *this;
    }

    friend modint operator+(const modint &x, const modint &y) { return modint(x) += y; }

    // 減法
    modint& operator-=(const modint &b){
        if ((x += mod - b.x) >= mod) x -= mod;
        return *this;
    }

    friend modint operator-(const modint &x, const modint &y) { return modint(x) -= y; }

    // 乗法
    modint& operator*=(const modint &b){
        (x *= b.x) %= mod;
        return *this;
    }

    friend modint operator*(const modint &x, const modint &y) { return modint(x) *= y; }

    // 除法
    modint& operator/=(const modint &b){ return (*this) *= b.inverse(); }

    friend modint operator/(const modint &x, const modint &y) { return modint(x) /= y; }

    modint inverse() const {
        int64_t s = 1, t = 0;
        int64_t a = x, b = mod;

        while (b > 0) {
            int64_t q = a / b;

            a -= q * b; swap(a, b);
            s -= q * t; swap(s, t);
        }

        assert (a == 1);

        return modint(s);
    }

    // 比較
    friend bool operator==(const modint &a, const modint &b) { return (a.x == b.x); }
    friend bool operator!=(const modint &a, const modint &b) { return (a.x != b.x); }

    // 入力
    friend istream &operator>>(istream &is, modint &a) {
        is >> a.x;
        a.x = (a.x % mod + mod) % mod;
        return is;
    }

    // 出力
    friend ostream &operator<<(ostream &os, const modint &a) { return os << a.x; }
};
#line 3 "program.cpp"

const ll Mod = 998244353;
using mint = modint<Mod>;

mint solve() {
    int N; cin >> N;
    string S_suf; cin >> S_suf;
    string S = '*' + S_suf;

    vector<mint> inv(N + 2); inv[1] = 1;
    for (int x = 2; x <= N + 1; x++) {
        ll q, r;
        tie (q, r) = divmod(Mod, x);
        inv[x] = -q * inv[r];
    }

    S[N] = 'B';
    mint total(0);
    ll g = 0;
    for (int i = 1; i <= N; i++) {
        if (S[i] == 'G') { g++; continue; }

        ll a = (g + 1) * (g + 2) % Mod;
        total += a * inv[i + 1];
        g = 0;
    }

    mint coef = mint(N + 1) / mint(2);

    return coef * total;
}

int main() {
    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << solve() << endl;
    }
};
yukicoder

結果

ソースコード
