問題一覧 > 通常問題

No.2943 Sigma String of String Score Problem

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : kazuppakazuppa / テスター : highlighterhighlighter MagentorMagentor hirayuu_ychirayuu_yc
0 ProblemId : 11370 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 21:20:00

裏話

実はこれが思いついた直前にプ●●●のF●●●r!のA●●●●DをAPしたのよ。

初A●●●●D 30のAPだったからうれしかったわけ。

で、でよ。この時思ったんだけど、

・AP

・A●●●●D

・kazuppa

これ全部APみたいなのが含まれてるじゃんって。

問題文

この問題は0-indexedで考えます。

$F(s,t,i)$ を次のように定義します。

  • 文字列 $u$ があります。始めは空です。
  • $j=0,1,...\ ,|s|-1$ について、もし $2^j\lor i=i$ なら $u$ の末尾に $s_j$ を追加します。
    • つまり、 $i$ を2進数表記したときに $j$ 桁目が $1$ なら、$u$ の末尾に $s_j$ を追加するということです。
  • そして、 $F(s,t,i)$ は上記の操作によってできた $u$ の部分文字列に含まれる $t$ の個数です。
たとえば、$F($aabc,ac$, 11)$ においての $u$ は aac となります。

そして、$u$ に acという部分文字列は $2$ つ含まれているので、 $F($aabc,ac$, 11)=2$ となります。

このとき、文字列 $S$ と $T$ が与えられるので、 $\displaystyle\sum_{i=0}^{2^{|S|}-1} F(S,T,i)$ を $998244353$ で割った余りを求めてください。

なお、この問題において部分文字列を、文字列から $0$ 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる文字列と定義します。

入力

入力は以下の形式で標準入力から与えられる。 
$S\ T$

制約

  • $1\leq |T|\leq |S| \leq 10^5$
  • $|T|\leq 10^3$
  • $S,T$ はともに英小文字からなる

出力

最後に改行してください。

サンプル

サンプル1
入力
aab ab
出力
4

例えば $i=0$ のとき、 $u=$(空)となります。 $u$ の部分文字列に含まれるab の個数は $0$ です。

また、 $i=5$ のとき、 $u=$abとなります。 $u$ の部分文字列に含まれる ab の個数は $1$ です。

こんな感じで考えていったとき、答えは $0+0+0+0+0+1+1+2=4$ となります。

サンプル2
入力
abc abd
出力
0

答えが $0$ の可能性もあります。

サンプル3
入力
kazuppa ap
出力
64

スコアはまあまあですね。

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