結果
| 問題 | No.2524 Stripes |
| コンテスト | |
| ユーザー |
 askr58
|
| 提出日時 | 2026-10-27 02:22:42 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 740 ms / 7,000 ms |
| + 152µs | |
| コード長 | 13,510 bytes |
| 記録 | |
| コンパイル時間 | 3,955 ms |
| コンパイル使用メモリ | 347,948 KB |
| 実行使用メモリ | 9,872 KB |
| 最終ジャッジ日時 | 2026-10-27 02:22:58 |
| 合計ジャッジ時間 | 14,142 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge5_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
// SPDX-License-Identifier: CC0-1.0
//
// [English]
// To the extent possible under law, the author(s) have dedicated all copyright
// and related and neighboring rights to this software to the public domain
// worldwide. This software is distributed without any warranty.
// See <https://creativecommons.org/publicdomain/zero/1.0/> for details.
//
// [日本語]
// 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および
// 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに
// 提供しています。本ソフトウェアは一切の保証なく配布されます。
// 自由にコピー・改変・再配布・商用利用できます（クレジット表記は不要です）。
// 詳細は <https://creativecommons.org/publicdomain/zero/1.0/deed.ja> を参照してください。
// ※ 英語の文面および CC0 1.0 の正式な条文（英語）が優先されます。
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
#include <atcoder/all>
using mint=atcoder::modint998244353;
ostream& operator<<(ostream& os,const mint& x){
os<<x.val();
return os;
}
istream& operator>>(istream& is,mint& x){
int t;
is>>t;
x=t;
return is;
}
template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);
template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
os<<p.first<<" "<<p.second;
return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
is>>p.first>>p.second;
return is;
}
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
for(int i=0;i<n;i++)is>>arr[i];
return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
for(int i=0;i<(int)vec.size();i++)os<<vec[i]<<(i+1==(int)vec.size()?"":" ");
return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
for(int i=0;i<(int)vec.size();i++)is>>vec[i];
return is;
}
template<class... Vecs>
void input_vec(Vecs&... vs) {
const auto n = get<0>(tie(vs...)).size();
for (size_t i = 0; i < n; ++i)
((cin >> vs[i]), ...);
}
template <class... Vecs>
void output_vec(const Vecs&... vs) {
const auto n = get<0>(tie(vs...)).size();
for (size_t i = 0; i < n; ++i) {
bool first = true;
(((cout << (exchange(first, false) ? "" : " ") << vs[i])), ...);
cout << endl;
}
}
template <typename T>
vector<T> make_unique(vector<T> vec){
ranges::sort(vec);
vec.erase(unique(vec.begin(),vec.end()),vec.end());
return vec;
}
vector<int> Iota(int n,int s=0){
vector<int> res(n);
iota(res.begin(),res.end(),s);
return res;
}
vector<ll> Iotall(int n,ll s=0){
vector<ll> res(n);
iota(res.begin(),res.end(),s);
return res;
}
void YESNO(bool f){
if(f)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;
//https://judge.yosupo.jp/submission/410350
//geneerated by Codex outside of contest time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>
#include <atcoder/convolution>
#include <atcoder/modint>
template <class Field = atcoder::modint998244353>
class FPS {
public:
using value_type = Field;
using size_type = std::size_t;
// 長さ n の零形式的冪級数を作る。
explicit FPS(size_type n = 0) : coefficients_(n) {}
// 長さ n で全ての係数が v の形式的冪級数を作る。
template <class U>
explicit FPS(size_type n = 0, U v = 0) : coefficients_(n, v) {}
// Field に変換できる型 U の係数列から作る。
explicit FPS(std::initializer_list<Field> coefficients)
: coefficients_(coefficients) {}
template <class U>
explicit FPS(const std::vector<U>& coefficients) {
coefficients_.reserve(coefficients.size());
for (const auto& coefficient : coefficients) {
coefficients_.emplace_back(coefficient);
}
}
size_type size() const noexcept {
return coefficients_.size();
}
void resize(size_type n) {
coefficients_.resize(n);
}
Field& operator[](size_type i) {
return coefficients_[i];
}
const Field& operator[](size_type i) const {
return coefficients_[i];
}
const std::vector<Field> to_vector() const{
return coefficients_;
}
FPS& operator+=(const FPS& rhs) {
const size_type old_size = size();
resize(std::max(size(), rhs.size()));
for (size_type i = 0; i < rhs.size(); ++i) {
if (i < old_size) {
coefficients_[i] += rhs[i];
} else {
coefficients_[i] = rhs[i];
}
}
return *this;
}
FPS& operator-=(const FPS& rhs) {
const size_type old_size = size();
resize(std::max(size(), rhs.size()));
for (size_type i = 0; i < rhs.size(); ++i) {
if (i < old_size) {
coefficients_[i] -= rhs[i];
} else {
coefficients_[i] = -rhs[i];
}
}
return *this;
}
FPS& operator*=(const FPS& rhs) {
return *this = *this * rhs;
}
// スカラーとの加減算は定数項だけに作用する。
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
FPS& operator+=(const U& rhs) {
if (size() == 0) {
resize(1);
}
coefficients_[0] += Field(rhs);
return *this;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
FPS& operator-=(const U& rhs) {
if (size() == 0) {
resize(1);
}
coefficients_[0] -= Field(rhs);
return *this;
}
// スカラー倍は convolution を使わず O(N) で行う。
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
FPS& operator*=(const U& rhs) {
const Field scalar(rhs);
for (auto& coefficient : coefficients_) {
coefficient *= scalar;
}
return *this;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
FPS& operator/=(const U& rhs) {
const Field scalar(rhs);
for (auto& coefficient : coefficients_) {
coefficient /= scalar;
}
return *this;
}
// 形式的微分を求める。
FPS derivative() const {
if (size() == 0) {
return FPS();
}
FPS result(size() - 1);
for (size_type i = 1; i < size(); ++i) {
result[i - 1] = coefficients_[i] * Field(i);
}
return result;
}
// 競技プログラミングで一般的な名前も用意する。
FPS diff() const {
return derivative();
}
// 定数項を 0 として形式的積分を求める。
FPS integral() const {
FPS result(size() + 1);
for (size_type i = 0; i < size(); ++i) {
result[i + 1] = coefficients_[i] / Field(i + 1);
}
return result;
}
// this * result == 1 (mod x^size()) となる乗法逆元を求める。
FPS inv() const {
assert(size() > 0 && coefficients_[0] != Field(0));
FPS result(std::vector<Field>{coefficients_[0].inv()});
while (result.size() < size()) {
const size_type next_size = std::min(size(), result.size() * 2);
FPS prefix(next_size);
for (size_type i = 0; i < next_size; ++i) {
prefix[i] = coefficients_[i];
}
FPS correction = prefix * result;
correction.resize(next_size);
for (auto& coefficient : correction.coefficients_) {
coefficient = -coefficient;
}
correction[0] += Field(2);
result *= correction;
result.resize(next_size);
}
return result;
}
// log(this) (mod x^size()) を O(N log N) で求める。
FPS log() const {
assert(size() > 0 && coefficients_[0] == Field(1));
FPS result = derivative() * inv();
result.resize(size() - 1);
result = result.integral();
result.resize(size());
return result;
}
// exp(this) (mod x^size()) を Newton 法により O(N log N) で求める。
FPS exp() const {
if (size() == 0) {
return FPS();
}
assert(coefficients_[0] == Field(0));
FPS result(std::vector<Field>{Field(1)});
while (result.size() < size()) {
const size_type next_size = std::min(size(), result.size() * 2);
FPS prefix(next_size);
for (size_type i = 0; i < next_size; ++i) {
prefix[i] = coefficients_[i];
}
result.resize(next_size);
FPS correction = prefix - result.log();
correction[0] += Field(1);
result *= correction;
result.resize(next_size);
}
return result;
}
FPS& operator/=(const FPS& rhs) {
return *this = *this / rhs;
}
friend FPS operator+(FPS lhs, const FPS& rhs) {
lhs += rhs;
return lhs;
}
friend FPS operator-(FPS lhs, const FPS& rhs) {
lhs -= rhs;
return lhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator+(FPS lhs, const U& rhs) {
lhs += rhs;
return lhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator+(const U& lhs, FPS rhs) {
rhs += lhs;
return rhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator-(FPS lhs, const U& rhs) {
lhs -= rhs;
return lhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator-(const U& lhs, FPS rhs) {
for (auto& coefficient : rhs.coefficients_) {
coefficient = -coefficient;
}
rhs += lhs;
return rhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator*(FPS lhs, const U& rhs) {
lhs *= rhs;
return lhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator*(const U& lhs, FPS rhs) {
rhs *= lhs;
return rhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator/(FPS lhs, const U& rhs) {
lhs /= rhs;
return lhs;
}
template <class U,
std::enable_if_t<std::is_constructible_v<Field, U>, int> = 0>
friend FPS operator/(const U& lhs, const FPS& rhs) {
FPS result = rhs.inv();
result *= lhs;
return result;
}
// atcoder::convolution への依存は積の定義だけに閉じ込める。
friend FPS operator*(const FPS& lhs, const FPS& rhs) {
return FPS(atcoder::convolution(lhs.coefficients_, rhs.coefficients_));
}
friend FPS operator/(const FPS& lhs, FPS rhs) {
if (lhs.size() == 0) {
return FPS();
}
rhs.resize(std::max(rhs.size(), lhs.size()));
FPS quotient = lhs * rhs.inv();
quotient.resize(std::max(lhs.size(), rhs.size()));
return quotient;
}
private:
std::vector<Field> coefficients_;
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout<<fixed<<setprecision(10);
int n;
cin>>n;
string s;
cin>>s;
vi a(n);
for(int i=0;i<n;i++)a[i]=(s[i]=='R');
using FPS=FPS<>;
using S=array<FPS,4>;
vector<mint> ans(n+1);
auto rec=[&](auto rec,int l,int r)->S{
if(l+1==r){
if(a[l]==1)return S{FPS{},FPS{},FPS{},FPS{0,1}};
else return S{FPS{0,1},FPS{},FPS{},FPS{}};
}
int c=(l+r)/2;
auto fs=rec(rec,l,c),gs=rec(rec,c,r);
S res;
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if((i&1)!=((j&2)>>1))res[(i&2)+(j&1)]+=fs[i]*gs[j];
for(int i=0;i<4;i++){
res[i].resize(r-l+1);
for(int j=0;j<fs[i].size();j++)res[i][j]+=fs[i][j];
for(int j=0;j<gs[i].size();j++)res[i][j]+=gs[i][j];
}
return res;
};
auto ret=rec(rec,0,n);
for(int i=0;i<4;i++){
ret[i].resize(n+1);
for(int j=1;j<=n;j++)ans[j]+=ret[i][j];
}
for(int i=0;i<n;i++)cout<<ans[i+1]<<endl;
}