問題一覧 > 通常問題

No.2943 Sigma String of String Score Problem

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 : kazuppa / テスター : highlighter Magentor hirayuu_yc
1 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)F(s,t,i) を次のように定義します。

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

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

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

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

入力

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

制約

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

出力

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

サンプル

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

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

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

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

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

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

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

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

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