結果

問題 No.2524 Stripes
ユーザー pockyny
提出日時 2023-10-27 22:24:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 875 ms / 7,000 ms
コード長 1,795 bytes
コンパイル時間 2,947 ms
コンパイル使用メモリ 140,520 KB
最終ジャッジ日時 2025-02-17 15:18:22
ジャッジサーバーID
(参考情報)
judge1 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <atcoder/segtree>
#include <atcoder/convolution>
#include <atcoder/modint>
#include <vector>
#include <string>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
struct S{
vector<mint> bb;
vector<mint> bw;
vector<mint> wb;
vector<mint> ww;
bool isE;
};
vector<mint> add(vector<mint> a,vector<mint> b){
if(a.size()<b.size()) swap(a,b);
vector<mint> c = a;
for(int i=0;i<b.size();i++) c[i] += b[i];
return c;
}
S op(S l,S r){
if(l.isE) return r;
if(r.isE) return l;
// bb
vector<mint> bb = add(add(add(convolution(l.bb,r.wb),convolution(l.bw,r.bb)),l.bb),r.bb);
// bw
vector<mint> bw = add(add(add(convolution(l.bb,r.ww),convolution(l.bw,r.bw)),l.bw),r.bw);
// wb
vector<mint> wb = add(add(add(convolution(l.wb,r.wb),convolution(l.ww,r.bb)),l.wb),r.wb);
// ww
vector<mint> ww = add(add(add(convolution(l.wb,r.ww),convolution(l.ww,r.bw)),l.ww),r.ww);
return {bb,bw,wb,ww};
}
S e(){
vector<mint> v = {1};
return {v,v,v,v,true};
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i,n; cin >> n;
string s; cin >> s;
vector<S> v(n);
vector<mint> bw = {0};
vector<mint> wb = {0};
for(i=0;i<n;i++){
if(s[i]=='R'){
vector<mint> bb = {0};
vector<mint> ww = {0,1};
v[i] = {bb,bw,wb,ww};
}else{
vector<mint> bb = {0,1};
vector<mint> ww = {0};
v[i] = {bb,bw,wb,ww};
}
}
segtree<S,op,e> seg(v);
S ans = seg.all_prod();
vector<mint> ans2 = add(add(ans.bb,ans.bw),add(ans.wb,ans.ww));
if(ans2.size()<n + 1) ans2.resize(n + 1);
for(i=1;i<=n;i++){
cout << ans2[i].val() << "\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0