#970216 (C++23) No.2720 Sum of Subarray of Subsequence of...

提出ソース
結果

問題	No.2720 Sum of Subarray of Subsequence of...
ユーザー	rogi52
提出日時	2024-04-06 04:03:28
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	883 ms / 4,000 ms
コード長	30,263 bytes
コンパイル時間	4,676 ms
コンパイル使用メモリ	291,752 KB
実行使用メモリ	30,512 KB
最終ジャッジ日時	2024-04-06 04:03:41
合計ジャッジ時間	12,881 ms
ジャッジサーバーID （参考情報）	judge14 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	2 ms 6,676 KB
testcase_13	AC	2 ms 6,676 KB
testcase_14	AC	64 ms 7,516 KB
testcase_15	AC	240 ms 10,764 KB
testcase_16	AC	280 ms 12,096 KB
testcase_17	AC	337 ms 13,192 KB
testcase_18	AC	360 ms 14,044 KB
testcase_19	AC	390 ms 15,392 KB
testcase_20	AC	450 ms 16,204 KB
testcase_21	AC	441 ms 16,984 KB
testcase_22	AC	484 ms 17,604 KB
testcase_23	AC	473 ms 18,260 KB
testcase_24	AC	494 ms 21,204 KB
testcase_25	AC	2 ms 6,676 KB
testcase_26	AC	2 ms 6,676 KB
testcase_27	AC	221 ms 11,548 KB
testcase_28	AC	64 ms 6,960 KB
testcase_29	AC	64 ms 6,960 KB
testcase_30	AC	883 ms 30,512 KB
testcase_31	AC	852 ms 29,992 KB
testcase_32	AC	377 ms 15,276 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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);
}
yukicoder

結果

テストケース

ソースコード
