結果

問題 No.3370 AB → BA
コンテスト
ユーザー Fu
提出日時 2025-11-17 21:46:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,273 bytes
コンパイル時間 4,215 ms
コンパイル使用メモリ 234,508 KB
実行使用メモリ 35,208 KB
最終ジャッジ日時 2025-11-17 21:46:25
合計ジャッジ時間 6,307 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef modint998244353 mint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i <= (int)(n); i++)
istream& operator>>(istream& is,mint& m) {
  long long val;
  is>>val;
  m=val;
  return is;
}
vector<mint> PTS(vector<mint> P,mint c){
  int n=P.size()-1;
  vector<mint> fact(n+1);
  vector<mint> invfact(n+1);
  vector<mint> cc(n+1);
  fact[0]=1;
  invfact[0]=1;
  cc[0]=1;
  rrep(i,n){
    fact[i]=fact[i-1]*i;
    cc[i]=cc[i-1]*c;
  }
  invfact[n]=fact[n].inv();
  for(int i=n-1;i>=1;i--) invfact[i]=invfact[i+1]*(i+1);
  vector<mint> X1(n+1);
  vector<mint> X2(n+1);
  rep(i,n+1){
    X1[i]=P[n-i]*fact[n-i];
    X2[i]=cc[i]*invfact[i];
  }
  vector<mint> X=convolution(X1,X2);
  vector<mint> ans(n+1);
  rep(i,n+1){
    ans[i]=X[n-i]*invfact[i];
  }
  return ans;
}
vector<mint> inv(const vector<mint>& f, int n) {
    assert(n > 0);
    assert(f.size() > 0 && f[0].val() != 0);
    vector<mint> H(1);
    H[0] = f[0].inv();
    
    int k = 1;
    while (k < n) {
        int k2 = k * 2;
        vector<mint> f_k(f.begin(), f.begin() + min((int)f.size(), k2));
        if (f_k.size() < k2) f_k.resize(k2, 0);
        vector<mint> H_k = H;
        H_k.resize(k2, 0);
        vector<mint> fH = convolution(f_k, H_k);
        vector<mint> T(k2);
        for(int i = 0; i < k2; i++) {
            T[i] = -fH[i];
        }
        T[0] += 2;
        H.resize(k2, 0);
        H = convolution(H, T);
        H.resize(k2);
        k = k2;
    }
    H.resize(n);
    return H;
}
int C=4000009;
vector<mint> fact(C+1),invfact(C+1);
mint binom(int n,int r){
  if (r>n) return 0;
  else{
    return fact[n]*invfact[r]*invfact[n-r];
  }
}
int main(){
  fact[0]=1;
  invfact[0]=1;
  rrep(i,C) fact[i]=fact[i-1]*i;
  invfact[C]=fact[C].inv();
  for(int i=C-1;i>=1;i--) invfact[i]=invfact[i+1]*(i+1);
  string s;
  cin>>s;
  int n=s.size();
  mint ans=1;
  rrep(i,n-1){
    if(s[i-1]=='B' &&s[i]=='A'){
      int a=0;
      int b=0;
      int k=i-1;
      while(k>=0 && s[k]=='B'){
        b++;
        k--;
      }
      k=i;
      while(k<n && s[k]=='A'){
        a++;
        k++;
      }
      ans*=binom(a+b,a);
    }
  }
  cout<<ans.val()<<endl;
}
0