結果
| 問題 | No.2720 Sum of Subarray of Subsequence of... |
| ユーザー |
 Challestend Rehtorbegnaro
|
| 提出日時 | 2024-04-11 18:27:16 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 616 ms / 4,000 ms |
| コード長 | 5,518 bytes |
| コンパイル時間 | 543 ms |
| コンパイル使用メモリ | 58,796 KB |
| 実行使用メモリ | 37,956 KB |
| 最終ジャッジ日時 | 2024-10-02 21:41:03 |
| 合計ジャッジ時間 | 7,964 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#include <cstdio>#include <algorithm>#include <set>#include <vector>#define limit 524288#define maxlog 20#define mod 998244353#define maxn 100000namespace cltstream{#define size 1048576char cltin[size + 1], *ih = cltin, *it = cltin;inline char gc(){#ifdef ONLINE_JUDGEif (ih == it){it = (ih = cltin) + fread(cltin, 1, size, stdin);if (ih == it)return EOF;}return *ih++;#elsereturn getchar();#endif}char cltout[size + 1], *oh = cltout, *ot = cltout + size;inline void pc(char c){if (oh == ot){fwrite(cltout, 1, size, stdout);oh = cltout;}*oh++ = c;}#define clop() fwrite(cltstream::cltout, 1, cltstream::oh - cltstream::cltout, stdout), cltstream::oh = cltstream::cltout#undef sizetemplate <typename _tp>inline void read(_tp& x){char c = gc();for (; c != 45 && (c < 48 || c > 57) && c != EOF; c = gc());int sgn = c == 45 ? c = gc(), -1 : 1;for (x = 0; c >= 48 && c <= 57 && c != EOF; x = (x << 3) + (x << 1) + (c ^ 48), c = gc());x *= sgn;}template <typename _tp>inline void write(_tp x, char text = -1){if (x < 0)pc(45), x = -x;if (!x)pc(48);else{int digit[22];for (digit[0] = 0; x; digit[++digit[0]] = x % 10, x /= 10);for (; digit[0]; pc(digit[digit[0]--] ^ 48));}if (text >= 0)pc(text);}inline void put(char str[], char text = -1){for (int cur = 0; str[cur]; pc(str[cur++]));if (text >= 0)pc(text);}}int unit[2][24];int inv[limit], fac[limit], fav[limit];int rev[limit];inline int add(int a, int b) {return a + b < mod ? a + b : a + b - mod;}inline int sub(int a, int b) {return a - b >= 0 ? a - b : a - b + mod;}inline int pow(int a, int n) {int res = 1;for (; n; n >>= 1, a = 1LL * a * a % mod)if (n & 1)res = 1LL * res * a % mod;return res;}inline int C(int n, int m) {if (m >= 0 && m <= n)return 1LL * fac[n] * fav[m] % mod * fav[n - m] % mod;elsereturn 0;}inline void InitIntUnit() {unit[0][23] = pow(3, 119);unit[1][23] = pow(332748118, 119);for(int i = 0; i < 2; ++i)for(int j = 22; j >= 0; --j)unit[i][j] = 1LL * unit[i][j + 1] * unit[i][j + 1] % mod;}inline void InitFac() {inv[1] = 1;for (int i = 2; i < limit; ++i)inv[i] = sub(0, 1LL * (mod / i) * inv[mod % i] % mod);fac[0] = fav[0] = 1;for (int i = 1; i < limit; ++i) {fac[i] = 1LL * fac[i - 1] * i % mod;fav[i] = 1LL * fav[i - 1] * inv[i] % mod;}}inline void Derivative(int F[], int n, int G[]) {for (int i = 0; i < n; ++i)G[i] = 1LL * (i + 1) * F[i + 1] % mod;G[n] = 0;}inline void Integration(int F[], int n, int G[], int C) {for (int i = n + 1; i > 0; --i)G[i] = 1LL * inv[i] * F[i - 1] % mod;G[0] = C;}inline void NTT(int F[], int N, int tp, int A[]) {for (int i = 0; i < N; ++i)A[i] = F[rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (N >> 1) : 0)];for (int k = 1, p = 1; p < N; ++k, p <<= 1)for (int i = 0; i < N; i += p << 1)for (int j = i, tmp = 1; j < i + p; ++j, tmp = 1LL * tmp * unit[tp][k] % mod) {int x = A[j], y = 1LL * A[j + p] * tmp % mod;A[j] = add(x, y);A[j + p] = sub(x, y);}if (tp == 1) {int v = pow(N, mod - 2);for (int i = 0; i < N; ++i)A[i] = 1LL * A[i] * v % mod;}}inline void Prod(int F[], int n, int G[], int m, int H[]) {static int A[limit], B[limit], C[limit];int N = 1;for (; N < n + m + 1; N <<= 1);for (int i = n + 1; i < N; ++i)F[i] = 0;for (int i = m + 1; i < N; ++i)G[i] = 0;NTT(F, N, 0, A);NTT(G, N, 0, B);for (int i = 0; i < N; ++i)C[i] = 1LL * A[i] * B[i] % mod;NTT(C, N, 1, H);for (int i = n + m + 1; i < N; ++i)H[i] = 0;}inline void Inv(int F[], int n, int G[]) {static int tmp[limit], res[limit];res[0] = pow(F[0], mod - 2);for (int i = 1; i - 1 < n; i <<= 1) {for (int j = 0; j < 2 * i; ++j)tmp[j] = F[j];Prod(tmp, 2 * i - 1, res, i - 1, tmp);for (int j = 0; j < 2 * i; ++j)tmp[j] = sub(0, tmp[j]);tmp[0] = add(tmp[0], 2);Prod(tmp, 2 * i - 1, res, i - 1, res);}for (int i = 0; i <= n; ++i)G[i] = res[i];}int n, m;int a[maxn + 5];char s[maxn + 5];int cnt[maxn + 5];int f[limit], g[limit], h[limit];int pos[limit], neg[limit], invneg[limit], ans[limit];void dfs(int arr[], int cur, int l, int r) {if (l < r) {int mid = (l + r) >> 1;dfs(arr, cur << 1, l, mid);dfs(arr, cur << 1 | 1, mid + 1, r);f[0] = 1;for (int i = l; i <= mid; ++i)f[i - l + 1] = arr[i];g[0] = 1;for (int i = mid + 1; i <= r; ++i)g[i - mid] = arr[i];Prod(f, mid - l + 1, g, r - mid, h);for (int i = l; i <= r; ++i)arr[i] = h[i - l + 1];}}int main(){InitIntUnit();InitFac();cltstream::read(n);cltstream::read(m);for (int i = 1; i <= n; ++i)cltstream::read(a[i]);for (int i = 1; i <= m; ++i)for (; s[i] != 'a' && s[i] != 's'; s[i] = cltstream::gc());for (int i = m, j = 0; i >= 0; j += (s[i] == 's'), --i) {++cnt[j];--cnt[j + 1];}int poslen = 0;for (int i = 0; i <= m + 1; ++i)for (int j = 1; j <= cnt[i]; ++j)pos[++poslen] = sub(0, i);dfs(pos, 1, 1, poslen);pos[0] = 1;int neglen = 0;for (int i = 0; i <= m + 1; ++i)for (int j = 1; j <= -cnt[i]; ++j)neg[++neglen] = sub(0, i);dfs(neg, 1, 1, neglen);neg[0] = 1;Inv(neg, n, invneg);Prod(pos, poslen, invneg, n, ans);int sum = 0;for (int i = 1; i <= n; ++i)sum = add(sum, 1LL * ans[i - 1] * ans[n - i] % mod * a[i] % mod);cltstream::write(sum);clop();return 0;}