問題一覧 > 通常問題

No.2720 Sum of Subarray of Subsequence of...

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 15
作問者 : ecottea / テスター : akakimidori 👑 hamamu
お気に入りにしたユーザー ProblemId : 10587 / 自分の提出
問題文最終更新日: 2024-03-25 19:32:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 426 (順位表) の他の問題:

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$ and a string $S$ of length $M$ consisting only of a and s. Let $S_i$ denote the $i$-th character from the left of $S$.

Define functions $f_0, \ldots, f_M$, each of which takes a sequence and returns an integer, as follows:

  • For a sequence $B$, $f_0(B)$ is the sum of the elements of $B$.
  • For $i$ satisfying $1 \leq i \leq M$ and a sequence $B$,
    • if $S_i=$ a, $f_i(B)$ is the sum of $f_{i-1}(C)$ over all non-empty contiguous subarrays $C$ of $B$;
    • if $S_i=$ s, $f_i(B)$ is the sum of $f_{i-1}(C)$ over all non-empty (not necessarily contiguous) subsequences $C$ of $B$.

Find $f_M(A)$. Since the answer can be very large, print the answer modulo $998244353$.

Here, for both subsequences and contiguous subarrays, two that are equal as sequences are distinguished if the sets of indices of the chosen elements differ.

Constraints

  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 10^5$
  • $0 \leq A_i < 998244353$
  • $S$ is a string of length $M$ consisting only of a and s
  • All input numbers are integers

Input

The input is given from Standard Input in the following format:

$N \ M$
$A_1 \ \ldots \ A_N$
$S$

Output

Print the answer modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
3 2
1 2 3
as
Output
50

Since $S_2=$ s, $f_2(A)$ is the sum of $f_1(B)$ over all non-empty subsequences $B$ of $A$, so $$ f_2(A) = f_1((1, 2, 3)) + f_1((1, 2)) + f_1((1, 3)) + f_1((2, 3)) + f_1((1)) + f_1((2)) + f_1((3)) $$ holds. Since $S_1=$ a, $f_1(B)$ is the sum of $f_0(C) = (C \text{'s sum of elements})$ over all non-empty contiguous subarrays $C$ of $B$, and the value of each term is computed as follows:

  • $f_1((1, 2, 3)) = f_0((1, 2, 3)) + f_0((1, 2)) + f_0((2, 3)) + f_0((1)) + f_0((2)) + f_0((3)) = 6 + 3 + 5 + 1 + 2 + 3 = 20$
  • $f_1((1, 2)) = f_0((1, 2)) + f_0((1)) + f_0((2)) = 3 + 1 + 2 = 6$
  • $f_1((1, 3)) = f_0((1, 3)) + f_0((1)) + f_0((3)) = 4 + 1 + 3 = 8$
  • $f_1((2, 3)) = f_0((2, 3)) + f_0((2)) + f_0((3)) = 5 + 2 + 3 = 10$
  • $f_1((1)) = f_0((1)) = 1$
  • $f_1((2)) = f_0((2)) = 2$
  • $f_1((3)) = f_0((3)) = 3$

Therefore, $$ f_2(A) = 20 + 6 + 8 + 10 + 1 + 2 + 3 = 50 $$ is obtained.

Sample 2
Input
10 7
3 1 4 1 5 9 2 6 5 3
assasas
Output
671269716

Print the answer modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。