結果
| 問題 |
No.2720 Sum of Subarray of Subsequence of...
|
| コンテスト | |
| ユーザー |
 rogi52
|
| 提出日時 | 2024-04-06 04:03:28 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 760 ms / 4,000 ms |
| コード長 | 30,263 bytes |
| コンパイル時間 | 4,569 ms |
| コンパイル使用メモリ | 291,652 KB |
| 実行使用メモリ | 30,648 KB |
| 最終ジャッジ日時 | 2024-10-01 03:40:55 |
| 合計ジャッジ時間 | 10,310 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#line 2 "cp-library/src/cp-template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template < class T, class U > T ceil (T x, U y) { return (x > 0 ? (x + y - 1) / y : x / y); }
template < class T, class U > T floor(T x, U y) { return (x > 0 ? x / y : (x - y + 1) / y); }
int popcnt(i32 x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
#line 2 "cp-library/src/utility/rep_itr.hpp"
template < class T > struct itr_rep {
T i, d;
constexpr itr_rep(const T i) noexcept : i(i), d(1) {}
constexpr itr_rep(const T i, const T d) noexcept : i(i), d(d) {}
void operator++() noexcept { i += d; }
constexpr int operator*() const noexcept { return i; }
constexpr bool operator!=(const itr_rep x) const noexcept { return d > 0 ? i < x.i : i > x.i; }
};
template < class T > struct rep {
const itr_rep< T > s, t;
constexpr rep(const T t) noexcept : s(0), t(t) {}
constexpr rep(const T s, const T t) noexcept : s(s), t(t) {}
constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {}
constexpr auto begin() const noexcept { return s; }
constexpr auto end () const noexcept { return t; }
};
template < class T > struct revrep {
const itr_rep < T > s, t;
constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {}
constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {}
constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {}
constexpr auto begin() const noexcept { return s; }
constexpr auto end () const noexcept { return t; }
};
#line 3 "cp-library/src/utility/io.hpp"
/* 128bit integer */
istream& operator>>(istream& is, i128& x) {
std::string s; is >> s;
int pm = (s[0] == '-');
x = 0;
for(int i : rep(pm, int(s.size()))) x = x * 10 + (s[i] - '0');
if(pm) x *= -1;
return is;
}
ostream& operator<<(ostream& os, const i128& x) {
if(x == 0) return os << '0';
i128 y = x;
if(y < 0) { os << '-'; y *= -1; }
std::vector<int> ny;
while(y > 0) { ny.push_back(y % 10); y /= 10; }
for(int i : revrep(ny.size())) os << ny[i];
return os;
}
template < class S, class T > istream& operator>>(istream& is, std::pair< S, T >& x) { is >> x.first >> x.second; return is; }
template < class S, class T > ostream& operator<<(ostream& os, const std::pair< S, T >& x) { os << x.first << " " << x.second; return os; }
namespace scanner {
struct sca {
template < class T > operator T() {
T s; std::cin >> s; return s;
}
};
struct vec {
int n;
vec(int n) : n(n) {}
template < class T > operator std::vector< T >() {
std::vector< T > v(n);
for(T& x : v) std::cin >> x;
return v;
}
};
struct mat {
int h, w;
mat(int h, int w) : h(h), w(w) {}
template < class T > operator std::vector< std::vector< T > >() {
std::vector m(h, std::vector< T >(w));
for(std::vector< T >& v : m) for(T& x : v) std::cin >> x;
return m;
}
};
struct speedup {
speedup() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
}
} speedup_instance;
}
scanner::sca in() { return scanner::sca(); }
scanner::vec in(int n) { return scanner::vec(n); }
scanner::mat in(int h, int w) { return scanner::mat(h, w); }
namespace printer {
void precision(int d) { std::cout << std::fixed << std::setprecision(d); }
void flush() { std::cout.flush(); }
}
template < class T >
ostream& operator<<(ostream& os, const std::vector< T > a) {
int n = a.size();
for(int i : rep(n)) { os << a[i]; if(i != n - 1) os << ' '; }
return os;
}
int print() { std::cout << '\n'; return 0; }
template < class head, class... tail > int print(head&& h, tail&&... t) {
std::cout << h; if(sizeof...(tail)) std::cout << ' ';
return print(std::forward<tail>(t)...);
}
template < class T > int print_n(const std::vector< T > a) {
int n = a.size();
for(int i : rep(n)) std::cout << a[i] << "\n";
return 0;
}
#line 2 "cp-library/src/utility/key_val.hpp"
template < class K, class V >
struct key_val {
K key; V val;
key_val() {}
key_val(K key, V val) : key(key), val(val) {}
template < std::size_t Index >
std::tuple_element_t< Index, key_val >& get() {
if constexpr (Index == 0) return key;
if constexpr (Index == 1) return val;
}
};
namespace std {
template < class K, class V > struct tuple_size < key_val< K, V > > : integral_constant< size_t, 2 > {};
template < class K, class V > struct tuple_element < 0, key_val< K, V > > { using type = K; };
template < class K, class V > struct tuple_element < 1, key_val< K, V > > { using type = V; };
}
#line 2 "cp-library/src/utility/vec_op.hpp"
template < class T > key_val< int, T > max_of(const vector< T >& a) {
int i = std::max_element(a.begin(), a.end()) - a.begin();
return {i, a[i]};
}
template < class T > key_val< int, T > min_of(const vector< T >& a) {
int i = std::min_element(a.begin(), a.end()) - a.begin();
return {i, a[i]};
}
template < class S, class T > S sum_of(const vector< T >& a) {
S sum = 0;
for(const T x : a) sum += x;
return sum;
}
template < class S, class T > vector< S > freq_of(const vector< T >& a, T L, T R) {
vector< S > res(R - L, S(0));
for(const T x : a) res[x - L] += 1;
return res;
}
template < class S, class T > struct prefix_sum {
vector< S > s;
prefix_sum(const vector< T >& a) : s(a) {
s.insert(s.begin(), S(0));
for(int i : rep(a.size())) s[i + 1] += s[i];
}
// [L, R)
S sum(int L, int R) { return s[R] - s[L]; }
};
#line 3 "cp-library/src/utility/heap.hpp"
template < class T > using heap_min = std::priority_queue< T, std::vector< T >, std::greater< T > >;
template < class T > using heap_max = std::priority_queue< T, std::vector< T >, std::less< T > >;
#line 27 "cp-library/src/cp-template.hpp"
#line 1 "cp-library/src/algorithm/bin_search.hpp"
template < class T, class F >
T bin_search(T ok, T ng, F f) {
while(abs(ng - ok) > 1) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template < class T, class F >
T bin_search_real(T ok, T ng, F f, int step = 80) {
while(step--) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
#line 2 "cp-library/src/algorithm/argsort.hpp"
template < class T > std::vector< int > argsort(const std::vector< T > &a) {
std::vector< int > ids((int)a.size());
std::iota(ids.begin(), ids.end(), 0);
std::sort(ids.begin(), ids.end(), [&](int i, int j) {
return a[i] < a[j] || (a[i] == a[j] && i < j);
});
return ids;
}
#line 1 "macro.hpp"
namespace macro {
using size_type = int;
template < class container > void sort(container& a) { std::sort(std:: begin(a), std:: end(a)); }
template < class container > void rsort(container& a) { std::sort(std::rbegin(a), std::rend(a)); }
template < class container > void reverse(container& a) { std::reverse(std::begin(a), std::end(a)); }
template < class container > void unique(container& a) {
std::sort(std::begin(a), std::end(a));
a.erase(std::unique(std::begin(a), std::end(a)), std::end(a));
}
template < class container > container sorted(const container& a) { container b = a; sort(b); return std::move(b); }
template < class container > container rsorted(const container& a) { container b = a; rsort(b); return std::move(b); }
template < class container, class compare > void sort(container& a, const compare& cmp) { std::sort(std::begin(a), std::end(a), cmp); }
template < class container, class compare > container sorted(const container& a, const compare& cmp) { container b = a; sort(b, cmp); return std::move(b); }
template < class container, class value > size_type lower_bound(const container& a, const value& x) { return std::lower_bound(std::begin(a), std::end(a), x) - std::begin(a); }
template < class container, class value > size_type upper_bound(const container& a, const value& x) { return std::upper_bound(std::begin(a), std::end(a), x) - std::begin(a); }
const std::vector<std::pair<size_type, size_type>> dir4 = { {+1, 0}, {-1, 0}, { 0, +1}, { 0, -1} };
const std::vector<std::pair<size_type, size_type>> dir8 = { {-1, -1}, {-1, 0}, {-1, +1}, { 0, -1}, { 0, +1}, {+1, -1}, {+1, 0}, {+1, +1} };
#ifdef _DEBUG
#define debug(x) std::cout << "[" << __LINE__ << "] " << #x << ": " << x << std::endl
#else
#define debug(x)
#endif
template < class container > void concat(container& a, const container& b) {
a.insert(std::end(a), std::begin(b), std::end(b));
}
std::vector<size_type> iota(const size_type n) {
std::vector<size_type> I(n);
std::iota(std::begin(I), std::end(I), 0);
return I;
}
template < class container > std::vector<size_type> sort_idx(const container& a) {
const size_type n = a.size();
std::vector<size_type> I = iota(n);
std::sort(std::begin(I), std::end(I), [&](size_type i, size_type j) { return a[i] < a[j] or (a[i] == a[j] and i < j); });
return I;
}
template < class container, class compare > std::vector<size_type> sort_idx(const container& a, const compare& cmp) {
const size_type n = a.size();
std::vector<size_type> I = iota(n);
std::sort(std::begin(I), std::end(I), [&](size_type i, size_type j) { return cmp(a[i], a[j]) or (a[i] == a[j] and i < j); });
return std::move(I);
}
struct grid {
using size_type = int;
size_type H, W;
grid(const size_type H, const size_type W) : H(H), W(W) {}
bool contains(const size_type i, const size_type j) {
return 0 <= i and i < H and 0 <= j and j < W;
}
};
using f64 = long double;
} // namespace macro
using namespace macro;
#line 2 "cp-library/src/number/modint.hpp"
struct modinfo { uint mod, root, isprime; };
template < modinfo const &ref >
struct modint {
static constexpr uint const &mod = ref.mod;
static constexpr uint const &root = ref.root;
static constexpr uint const &isprime = ref.isprime;
uint v = 0;
constexpr modint& s(uint v) { this->v = v < mod ? v : v - mod; return *this; }
constexpr modint(ll v = 0) { s(v % mod + mod); }
modint operator-() const { return modint() - *this; }
modint& operator+=(const modint& rhs) { return s(v + rhs.v); }
modint& operator-=(const modint& rhs) { return s(v + mod - rhs.v); }
modint& operator*=(const modint& rhs) { v = ull(v) * rhs.v % mod; return *this; }
modint& operator/=(const modint& rhs) { return *this *= inv(rhs); }
modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }
friend modint pow(modint x, ll n) { modint res(1); while(n > 0) { if(n & 1) res *= x; x *= x; n >>= 1; } return res; }
friend modint inv(modint v) {
if(isprime) {
return pow(v, mod - 2);
} else {
ll a = v.v, b = modint::mod, x = 1, y = 0, t;
while(b > 0) { t = a / b; swap(a -= t * b, b); swap(x -= t * y, y); }
return modint(x);
}
}
friend modint operator+(int x, const modint& y) { return modint(x) + y; }
friend modint operator-(int x, const modint& y) { return modint(x) - y; }
friend modint operator*(int x, const modint& y) { return modint(x) * y; }
friend modint operator/(int x, const modint& y) { return modint(x) / y; }
friend istream& operator>>(istream& is, modint& m) { ll x; is >> x; m = modint(x); return is; }
friend ostream& operator<<(ostream& os, const modint& m) { return os << m.v; }
bool operator==(const modint& r) const { return v == r.v; }
bool operator!=(const modint& r) const { return v != r.v; }
static uint get_mod() { return mod; }
static int is_prime() { return isprime; }
};
constexpr modinfo base998244353 { 998244353, 3, 1 };
constexpr modinfo base1000000007 { 1000000007, 0, 1 };
using mint998244353 = modint< base998244353 >;
using mint1000000007 = modint< base1000000007 >;
#line 3 "cp-library/src/number/ntt.hpp"
namespace ntt {
template < class mint >
void trans(vector<mint>& v, bool is_inv) {
if(v.empty()) return;
int n = v.size();
uint mod = mint::mod, root = mint::root;
static bool first = true;
static vector<ll> vbw(30), vibw(30);
if(first) {
first = false;
for(int k : rep(30)) {
vbw[k] = pow(mint(root), (mod - 1) >> (k + 1)).v;
vibw[k] = inv(mint(vbw[k])).v;
}
}
for(int i = 0, j = 1; j < n - 1; j++) {
for(int k = n >> 1; k > (i ^= k); k >>= 1);
if(i > j) swap(v[i], v[j]);
}
for(int k = 0, t = 2; t <= n; ++k, t <<= 1) {
mint bw = (is_inv ? vibw[k] : vbw[k]);
for (int i = 0; i < n; i += t) {
mint w = 1;
for (int j = 0; j < t / 2; ++j) {
int j1 = i + j, j2 = i + j + t/2;
mint c1 = v[j1], c2 = v[j2] * w;
v[j1] = c1 + c2;
v[j2] = c1 - c2;
w *= bw;
}
}
}
if(is_inv) {
mint iv = inv(mint(n));
for(int i : rep(n)) v[i] *= iv;
}
}
template < class mint > void ntt(vector<mint>& v) { trans(v, false); }
template < class mint > void intt(vector<mint>& v) { trans(v, true); }
// for garner
constexpr modinfo base0 { 754974721, 11, 1};
constexpr modinfo base1 { 167772161, 3, 1};
constexpr modinfo base2 { 469762049, 3, 1};
using mint0 = modint< base0 >;
using mint1 = modint< base1 >;
using mint2 = modint< base2 >;
static const mint1 imod0 = 95869806; // MOD0^-1 mod MOD1
static const mint2 imod1 = 104391568; // MOD1^^1 mod MOD2
static const mint2 imod01 = 187290749; // imod1 / MOD0;
template < class T >
vector< T > naive(const vector< T >& a, const vector< T >& b) {
if(a.empty() || b.empty()) return {};
int n = a.size(), m = b.size();
vector< T > c(n + m - 1);
for(int i : rep(n)) for(int j : rep(m)) c[i + j] += a[i] * b[j];
return c;
}
template < class mint >
vector<mint> mul(const vector<mint>& a, const vector<mint>& b) {
if(a.empty() || b.empty()) return {};
int n = a.size(), m = b.size();
if(min(n, m) < 30) return naive(a, b);
uint mod = mint::mod;
int sz = [&]() {
int n2 = 1, m2 = 1;
while(n2 < n) n2 <<= 1;
while(m2 < m) m2 <<= 1;
return max(n2, m2) << 1;
}();
if(mod == 998244353) {
vector<mint> a2(sz, 0), b2(sz, 0), c(sz, 0);
for(int i : rep(n)) a2[i] = a[i];
for(int i : rep(m)) b2[i] = b[i];
ntt(a2), ntt(b2);
for(int i : rep(sz)) c[i] = a2[i] * b2[i];
intt(c);
c.resize(n + m - 1);
return c;
}
vector<mint0> a0(sz, 0), b0(sz, 0), c0(sz, 0);
vector<mint1> a1(sz, 0), b1(sz, 0), c1(sz, 0);
vector<mint2> a2(sz, 0), b2(sz, 0), c2(sz, 0);
for(int i : rep(n)) a0[i].v = a1[i].v = a2[i].v = a[i].v;
for(int i : rep(m)) b0[i].v = b1[i].v = b2[i].v = b[i].v;
ntt(a0), ntt(b0), ntt(a1), ntt(b1), ntt(a2), ntt(b2);
for(int i : rep(sz)) {
c0[i] = a0[i] * b0[i];
c1[i] = a1[i] * b1[i];
c2[i] = a2[i] * b2[i];
}
intt(c0), intt(c1), intt(c2);
vector<mint> c(n + m - 1);
static const mint mod0 = mint0::mod, mod01 = mod0 * mint1::mod;
for(int i : rep(n + m - 1)) {
ll y0 = c0[i].v;
ll y1 = (imod0 * (c1[i] - y0)).v;
ll y2 = (imod01 * (c2[i] - y0) - imod1 * y1).v;
c[i] = mod01 * y2 + mod0 * y1 + y0;
}
return c;
}
} // namespace ntt
#line 3 "cp-library/src/utility/random.hpp"
namespace randnum {
static uint seed;
static std::mt19937 mt;
struct gen_seed {
gen_seed() {
seed = std::random_device()();
mt = std::mt19937(seed);
}
} gs;
// [L, R)
template < class T >
T gen_int(T L, T R) {
return std::uniform_int_distribution< T >(L, R - 1)(mt);
}
template < class T >
T get_real(T L, T R) {
return std::uniform_real_distribution< T >(L, R)(mt);
}
}
#line 4 "cp-library/src/number/modfunc.hpp"
u64 modpow64(u64 a, u64 n, u64 mod) {
a %= mod;
u64 res = 1;
while(n > 0) {
if(n % 2 == 1) res = i128(res) * a % mod;
a = i128(a) * a % mod;
n /= 2;
}
return res;
}
u64 modpow(u64 a, u64 n, u64 mod) {
a %= mod;
u64 res = 1;
while(n > 0) {
if(n % 2 == 1) res = res * a % mod;
a = a * a % mod;
n /= 2;
}
return res;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
// solve x^2 = a (mod p)
// return x
// or No Solution (-1)
i32 modsqrt(i32 a, i32 p) {
if(p == 2) return a;
a %= p;
if(a == 0) return 0;
if(modpow(a, (p - 1) / 2, p) != 1) return -1;
i32 q = p - 1, m = 0; while(q % 2 == 0) q /= 2, m++;
i32 z; do { z = randnum::gen_int<i32>(1, p); } while(modpow(z, (p - 1) / 2, p) != p - 1);
i64 c = modpow(z, q, p), t = modpow(a, q, p), r = modpow(a, (q + 1) / 2, p);
while(m > 1) {
if(modpow(t, 1 << (m - 2), p) != 1) r = r * c % p, t = t * (c * c % p) % p;
c = c * c % p;
m -= 1;
}
return r;
}
#line 5 "cp-library/src/number/fps.hpp"
class undefined {};
template < class mint > struct fps : std::vector<mint> {
using std::vector<mint>::vector;
fps(const std::vector<mint>& f) : std::vector<mint>(f) {}
int size() const { return int(std::vector<mint>::size()); }
void ups(int s) { if(size() < s) this->resize(s, 0); }
fps low(int s) const {
return fps(this->begin(), this->begin() + min(this->size(), s));
}
fps rev() const {
return fps(this->rbegin(), this->rend());
}
fps operator-() const {
fps g = *this;
for(int i : rep(g.size())) g[i] = -g[i];
return g;
}
fps operator+(const mint& v) const { return fps(*this) += v; }
fps operator-(const mint& v) const { return fps(*this) -= v; }
fps operator*(const mint& v) const { return fps(*this) *= v; }
fps operator/(const mint& v) const { return fps(*this) /= v; }
fps operator+(const fps& r) const { return fps(*this) += r; }
fps operator-(const fps& r) const { return fps(*this) -= r; }
fps operator*(const fps& r) const { return fps(*this) *= r; }
fps operator/(const fps& r) const { return fps(*this) /= r; }
fps operator<<(int s) const { return fps(*this) <<= s; }
fps operator>>(int s) const { return fps(*this) >>= s; }
fps& operator+=(const fps& r) { ups(r.size()); for(int i : rep(r.size())) (*this)[i] += r[i]; return *this; }
fps& operator-=(const fps& r) { ups(r.size()); for(int i : rep(r.size())) (*this)[i] -= r[i]; return *this; }
fps& operator*=(const fps& r) { return *this = ntt::mul(*this, r); } // ntt
fps& operator/=(const fps& r) { return *this *= inv(r); }
template < class T > fps& operator+=(T v) { ups(1); (*this)[0] += v; return *this; }
template < class T > fps& operator-=(T v) { ups(1); (*this)[0] -= v; return *this; }
template < class T > fps& operator*=(T v) { for(auto &x : *this) x *= v; return *this; }
template < class T > fps& operator/=(T v) { assert(v != T(0)); return *this *= mint(1) / v; }
fps& operator<<=(int s) {
fps g(s, 0);
g.insert(g.end(), this->begin(), this->end());
return *this = g;
}
fps& operator>>=(int s) {
return *this = {this->begin() + s, this->end()};
}
friend fps differential(const fps& f) {
int n = f.size();
fps g(n - 1);
for(int i : rep(1, n)) g[i - 1] = f[i] * i;
return g;
}
friend fps integral_(const fps& f) { // std と衝突
int n = f.size();
fps g(n + 1, 0);
for(int i : rep(0, n)) g[i + 1] = f[i] / (i + 1);
return g;
}
friend fps inv(const fps& f, int deg) {
assert(f[0] != 0);
fps g = {mint(1) / f[0]};
for(int i = 1; i < deg; i <<= 1) {
g = (g + g - g * g * f.low(i << 1)).low(i << 1);
}
g.resize(deg);
return g;
}
friend fps log(const fps& f, int deg) {
assert(f[0] == 1);
fps g = integral_((differential(f) * inv(f, deg)));
g.resize(deg);
return g;
}
friend fps exp(const fps& f, int deg) {
assert(f[0] == 0);
fps g = {1};
for(int i = 1; i < deg; i <<= 1) {
g = g * (f.low(i << 1) - log(g, i << 1) + 1).low(i << 1);
}
g.resize(deg);
return g;
}
friend fps pow(const fps& f, ll n, int deg) {
if(n == 0) {
fps g(deg, 0);
g[0] = 1;
return g;
}
int i = 0;
while(i < f.size() and f[i] == 0) i++;
if(i == f.size() or i128(i) * n >= deg) return fps(deg, 0);
mint k = f[i];
fps g = exp(log((f >> i) / k, deg) * n, deg) * pow(k, n) << (i * n);
g.resize(deg);
return g;
}
friend fps sqrt(const fps& f, int deg) {
int n = f.size(), d = n;
for(int i : revrep(0, n)) if(f[i] != 0) d = i;
if(d == n) return f;
if(d % 2 == 1) throw undefined();
mint y = f[d], x = modsqrt(y.v, mint::get_mod());
if(x * x != y) throw undefined();
mint c = mint(1) / y;
fps g(n - d);
for(int i : rep(n - d)) g[i] = f[d + i] * c;
assert(g[0] == 1);
mint inv2 = mint(1) / 2;
fps h = {1};
for(int i = 1; i < deg; i <<= 1) {
h = (h + g.low(i << 1) * inv(h, i << 1)).low(i << 1);
for(mint& a : h) a *= inv2;
}
h.resize(deg);
for(int i : rep(deg)) h[i] *= x;
for(int i : revrep(deg)) h[i] = (i >= d / 2 ? h[i - d / 2] : 0);
return h;
}
friend fps inv(const fps& f) { return inv(f, f.size()); }
friend fps log(const fps& f) { return log(f, f.size()); }
friend fps exp(const fps& f) { return exp(f, f.size()); }
friend fps pow(const fps& f, ll n) { return pow(f, n, f.size()); }
friend fps sqrt(const fps& f) { return sqrt(f, f.size()); }
fps operator() (const fps<mint>& g) {
fps<mint>& f = *this;
assert(f.size() == g.size());
int n = f.size(), k = ceil(sqrt(n));
vector< fps<mint> > bs(k + 1);
bs[0] = {1};
for(int i : rep(k)) bs[i + 1] = (bs[i] * g).low(n);
vector< fps<mint> > gs(k + 1);
gs[0] = {1};
for(int i : rep(k)) gs[i + 1] = (gs[i] * bs[k]).low(n);
fps<mint> h(n);
for(int i : rep(0, n, k)) {
fps<mint> c;
for(int j : rep(i, min(i + k, n))) c += bs[j - i] * f[j];
h += (c * gs[i / k]).low(n);
}
return h;
}
};
#line 3 "cp-library/src/number/binom_mod.hpp"
template < class mint >
mint fact(int n) {
assert(0 <= n);
assert(mint::is_prime());
static const uint mod = mint::get_mod();
static std::vector<mint> data = {1, 1};
while(int(data.size()) <= n) {
int i = data.size();
data.push_back(data.back() * i);
}
return data[n];
}
template < class mint >
mint inv(int n) {
assert(0 <= n);
assert(mint::is_prime());
static const uint mod = mint::get_mod();
static std::vector<mint> data = {1, 1};
while(int(data.size()) <= n) {
int i = data.size();
data.push_back(- data[mod % i] * (mod / i));
}
return data[n];
}
template < class mint >
mint fact_inv(int n) {
assert(0 <= n);
assert(mint::is_prime());
static const uint mod = mint::get_mod();
static std::vector<mint> data = {1, 1};
while(int(data.size()) <= n) {
int i = data.size();
data.push_back(data.back() * inv<mint>(i));
}
return data[n];
}
template < class mint >
mint comb(int n, int k) {
if(k < 0 or n < k) return 0;
return fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k);
}
template < class mint >
mint perm(int n, int k) {
return fact<mint>(n) * fact_inv<mint>(n - k);
}
template < class mint >
mint homo(int n, int k) {
return comb<mint>(n + k - 1, k);
}
template < class mint > struct power {
mint a;
std::vector<mint> data = {1};
power() {}
power(const mint a) : a(a) {}
// a^n
mint get(const int n) {
assert(0 <= n);
while(int(data.size()) <= n)
data.push_back(data.back() * a);
return data[n];
}
};
#line 6 "cp-library/src/number/poly.hpp"
template < class mint > struct poly : std::vector<mint> {
using std::vector<mint>::vector;
poly(const std::vector<mint>& f) : std::vector<mint>(f) {}
int size() const { return int(std::vector<mint>::size()); }
void ups(int s) { if(size() < s) this->resize(s, 0); }
poly low(int s) const {
return poly(this->begin(), this->begin() + min(this->size(), s));
}
friend poly rev(const poly& f) {
return poly(f.rbegin(), f.rend());
}
poly operator-() const {
poly g = *this;
for(int i : rep(g.size())) g[i] = -g[i];
return g;
}
poly operator+(const mint& v) const { return poly(*this) += v; }
poly operator-(const mint& v) const { return poly(*this) -= v; }
poly operator*(const mint& v) const { return poly(*this) *= v; }
poly operator/(const mint& v) const { return poly(*this) /= v; }
poly operator+(const poly& r) const { return poly(*this) += r; }
poly operator-(const poly& r) const { return poly(*this) -= r; }
poly operator*(const poly& r) const { return poly(*this) *= r; }
poly operator/(const poly& r) const { return poly(*this) /= r; }
poly operator%(const poly& r) const { return poly(*this) %= r; }
poly operator<<(int s) const { return poly(*this) <<= s; }
poly operator>>(int s) const { return poly(*this) >>= s; }
poly& operator+=(const poly& r) { ups(r.size()); for(int i : rep(r.size())) (*this)[i] += r[i]; return *this; }
poly& operator-=(const poly& r) { ups(r.size()); for(int i : rep(r.size())) (*this)[i] -= r[i]; return *this; }
poly& operator*=(const poly& r) { return *this = ntt::mul(*this, r); }
poly& operator/=(const poly& r) {
assert(r.size() > 0);
assert(r.back() != 0);
int s = size() - r.size() + 1;
if(s <= 0) return *this = poly{0};
return *this = rev((rev(*this).low(s) * inv(fps<mint>(rev(r)), s).low(s)).low(s));
}
poly& operator%=(const poly& r) {
*this -= *this / r * r;
return *this = low(r.size() - 1);
}
template < class T > poly& operator+=(T v) { ups(1); (*this)[0] += v; return *this; }
template < class T > poly& operator-=(T v) { ups(1); (*this)[0] -= v; return *this; }
template < class T > poly& operator*=(T v) { for(auto &x : *this) x *= v; return *this; }
template < class T > poly& operator/=(T v) { assert(v != T(0)); return *this *= mint(1) / v; }
poly& operator<<=(int s) {
poly g(s, 0);
g.insert(g.end(), this->begin(), this->end());
return *this = g;
}
poly& operator>>=(int s) {
return *this = {this->begin() + s, this->end()};
}
friend poly differential(const poly& f) {
int n = f.size();
poly g(n - 1);
for(int i : rep(1, n)) g[i - 1] = f[i] * i;
return g;
}
friend poly integral_(const poly& f) { // std と衝突
int n = f.size();
poly g(n + 1, 0);
for(int i : rep(0, n)) g[i + 1] = f[i] / (i + 1);
return g;
}
friend poly taylor_shift(const poly& f, mint c) {
int n = f.size();
std::vector<mint> c_pow(n);
c_pow[0] = 1;
for(int i : rep(1, n)) c_pow[i] = c * c_pow[i - 1];
poly<mint> p(n), q(n);
for(int i : rep(n)) p[i] = f[i] * fact<mint>(i);
for(int i : rep(n)) q[i] = c_pow[i] * fact_inv<mint>(i);
poly<mint> r = (p * rev(q)) >> n - 1;
for(int i : rep(n)) r[i] *= fact_inv<mint>(i);
return r;
}
};
template < class mint >
poly<mint> all_product(vector< poly<mint> >& fs) {
if(int(fs.size()) == 0) return {1};
using P = std::pair<int, int>;
std::priority_queue< P, std::vector< P >, std::greater< P >> pq;
for(int i : rep(fs.size())) pq.push({fs[i].size(), i});
while(int(pq.size()) >= 2) {
auto [n1, i1] = pq.top(); pq.pop();
auto [n2, i2] = pq.top(); pq.pop();
fs[i1] *= fs[i2];
pq.push({n1 + n2, i1});
}
return fs[pq.top().second];
}
#line 6 "main.cpp"
int main() {
int N = in(), M = in();
using mint = mint998244353;
vector<mint> A = in(N);
string S = in();
vector<int> e = {-1};
int t = -1;
for(char c : S) {
if(c == 'a') {
e.back() -= 1;
t -= 1;
} else {
e.push_back(- 1 - t);
t = -1;
}
}
vector<poly<mint>> upper, lower; {
int c = -1;
while(not e.empty()) {
while(e.back() > 0) { upper.push_back(fps<mint>{1, c}); e.back()--; }
while(e.back() < 0) { lower.push_back(fps<mint>{1, c}); e.back()++; }
e.pop_back();
c -= 1;
}
}
vector<mint> F = all_product(upper) * inv(fps(all_product(lower)), N);
mint ans = 0;
for(int i : rep(N)) ans += A[i] * F[i] * F[N - 1 - i];
print(ans);
}