結果
| 問題 | No.3439 [Cherry 8th Tune] どの頂点にいた頃に戻りたいのか? |
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2024-05-08 00:37:18 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,468 bytes |
| 記録 | |
| コンパイル時間 | 5,427 ms |
| コンパイル使用メモリ | 341,320 KB |
| 実行使用メモリ | 161,352 KB |
| 最終ジャッジ日時 | 2026-01-23 20:51:42 |
| 合計ジャッジ時間 | 21,205 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 RE * 1 |
| other | RE * 37 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// マクロの定義
#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__)
// 除算に関する関数
template<typename T, typename U>
T floor(T x, U y){return (x>0 ? x/y: (x-y+1)/y);}
template<typename T, typename U>
T ceil(T x, U y){return (x>0 ? (x+y-1)/y: x/y);}
template<typename T, typename U>
T mod(T x, U y){
T q=floor(x,y);
return x-q*y;
}
template<typename T, typename U>
pair<T,T> divmod(T x, U y){
T q=floor(x,y);
return {q,x-q*y};
}
// 指数に関する関数
ll intpow(ll x, ll y){
ll a=1;
while (y){
if (y&1) a*=x;
x*=x;
y>>=1;
}
return a;
}
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;
}
ll sum(vector<int> &X){
ll y=0;
for (auto &&x: X) y+=x;
return y;
}
template<typename T>
T sum(vector<T> &X){
T y=T(0);
for (auto &&x: X) y+=x;
return y;
}
// max, min
template<typename T, typename U>
inline bool chmax(T &a, const U b){
return (a<b ? a=b, 1: 0);
}
template<typename T, typename U>
inline bool chmin(T &a, const U b){
return (a>b ? a=b, 1: 0);
}
template<class... T>
constexpr auto max(T... a){
return max(initializer_list<common_type_t<T...>>{a...});
}
template<class... T>
constexpr auto min(T... a){
return min(initializer_list<common_type_t<T...>>{a...});
}
template<class T>
T max(vector<T> X){
T alpha=X[0];
for (auto x:X) chmax(alpha, x);
return alpha;
}
template<class T>
T min(vector<T> X){
T alpha=X[0];
for (auto x:X) chmin(alpha, x);
return alpha;
}
//特別な演算
template<class T, class U>
pair<T,U> operator+(const pair<T,U> &lhs, const pair<T,U> &rhs){
return pair<T,U>(lhs.first + rhs.first, lhs.second + rhs.second);
}
template<class T, class U>
pair<T,U> operator-(const pair<T,U> &lhs, const pair<T,U> &rhs){
return pair<T,U>(lhs.first - rhs.first, lhs.second - rhs.second);
}
template<class T, class U>
pair<T,U> operator+=(pair<T,U> &lhs, const pair<T,U> &rhs){return lhs=lhs+rhs;}
template<class T, class U>
pair<T,U> operator-=(pair<T,U> &lhs, const pair<T,U> &rhs){return lhs=lhs-rhs;}
// 入出力
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 N=(int)len(X);
os << "[";
rep(i,N) os << (i ? ", ": "") << X[i];
return os << "]";
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &S){
os << "{{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}}";
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &S){
os << "{";
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){
os << "{{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}}";
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &S){
os << "{";
int i=0;
for (T a: S) {os << (i ? ", ": "") << a; i++;}
return os << "}";
}
template<typename A, typename T>
ostream &operator<<(ostream &os, const unordered_map<A,T> &M){
os << "{{";
int i=0;
for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;}
return os << "}}";
}
template<typename A, typename T>
ostream &operator<<(ostream &os, const map<A,T> &M){
os << "{";
int i=0;
for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;}
return os << "}";
}
template<const int mod>
struct modint{
int64_t a;
public:
// 初期化
constexpr modint (): a(0){}
constexpr modint (int64_t a): a((a%mod+mod)%mod) {}
// マイナス元
modint operator-() const { return modint(-a);}
// 加法
modint& operator+=(const modint &y){
if ((a+=y.a)>=mod) a-=mod;
return *this;
}
friend modint operator+(const modint &x, const modint &y) {return modint(x)+=y;}
// 減法
modint& operator-=(const modint &y){
if ((a+=mod-y.a)>=mod) a-=mod;
return *this;
}
friend modint operator-(const modint &x, const modint &y) {return modint(x)-=y;}
// 乗法
modint& operator*=(const modint &y){
(a*=y.a)%=mod;
return *this;
}
friend modint operator*(const modint &x, const modint &y) {return modint(x)*=y;}
// 除法
modint& operator/=(const modint &y){
return (*this)*=y.inverse();
}
friend modint operator/(const modint &x, const modint &y) {return modint(x)/=y;}
// モジュラー逆元
bool invertible() const{
int64_t x=a, y=mod;
while (y) swap(x%=y,y);
return x==1;
}
modint inverse() const{
int64_t s=1, t=0;
int64_t x=a, y=mod;
while (y){
auto q=x/y;
swap(x-=q*y,y);
swap(s-=q*t,t);
}
assert(x==1);
return modint(s);
}
// インクリメント
modint& operator++(){
if (++a==mod) a=0;
return *this;
}
modint operator++(int){
modint x(*this);
if (++a==mod) a=0;
return x;
}
// デクリメント
modint& operator--(){
if (a==0) a=mod-1;
else a--;
}
modint operator--(int){
modint x(*this);
if (a==0) a=mod-1;
else a--;
return x;
}
// 比較
friend bool operator==(const modint &x, const modint &y) { return (x.a==y.a);}
friend bool operator!=(const modint &x, const modint &y) { return (x.a!=y.a);}
// 入力
friend istream &operator>>(istream &is, modint &x) {
is >> x.a;
x.a=(x.a%mod+mod)%mod;
return (is);
}
// 出力
friend ostream &operator<<(ostream &os, const modint &x) { return os << x.a;}
};
template<int mod>
modint<mod> pow(modint<mod> x, int64_t n){
if (n<0) return pow(x,-n).inverse();
modint<mod> y(1);
while (n){
if (n&1) y*=x;
x*=x; n>>=1;
}
return y;
}
ll Mod = 998244353;
using F = modint<998244353>;
F solve(){
int N; cin >> N;
string S_suf; cin >> S_suf;
string S = "*" + S_suf;
vector<F> inv(N + 2, 1);
for (int x = 2; x <= N + 1; x ++){
int q, r;
tie (q, r) = divmod(Mod, x);
inv[x] = - q * inv[r];
}
S[N] = 'B';
F total(0);
long long g = 0;
for (int i = 1; i <= N; i ++){
if (S[i] == 'G'){g ++;}
else{
F a = (g + 1) * (g + 2);
total += a * inv[i + 1];
g = 0;
}
}
return (total * (N + 1)) / 2;
}
int main(){
int T; cin >> T;
for (int t = 1; t <= T; t ++){
cout << solve() << "\n";
}
}