問題一覧 > 通常問題

No.2943 Sigma String of String Score Problem

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 128 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 65
作問者 : kazuppa / テスター : highlighter Magentor hirayuu_yc
お気に入りにしたユーザー ProblemId : 11370 / 自分の提出
問題文最終更新日: 2024-10-18 21:20:00
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 450 (順位表) の他の問題:

Behind the Scenes

Actually, right before I came up with this, I had just gotten an AP on A●●●●D from F●●●r! in Pu●●●.

It was my first AP on a level 30 A●●●●D, so I was really happy.

So, anyway. Here's what I thought at that moment:

・AP

・A●●●●D

・kazuppa

All of these contain something like AP, don't they?

Problem Statement

In this problem, everything is 0-indexed.

Define $F(s,t,i)$ as follows.

  • There is a string $u$, which is initially empty.
  • For $j=0,1,...\ ,|s|-1$, if $2^j\lor i=i$, append $s_j$ to the end of $u$.
    • In other words, if the $j$-th digit of $i$ in binary is $1$, append $s_j$ to the end of $u$.
  • Then, $F(s,t,i)$ is the number of occurrences of $t$ among the substrings of the $u$ produced by the above operations.
For example, for $F($aabc,ac$, 11)$, $u$ is aac.

Since $u$ contains $2$ substrings equal to ac, we have $F($aabc,ac$, 11)=2$.

Given strings $S$ and $T$, find $\displaystyle\sum_{i=0}^{2^{|S|}-1} F(S,T,i)$ modulo $998244353$.

In this problem, a substring is defined as a string obtained by removing $0$ or more elements from a string and concatenating the remaining elements in their original order.

Input

The input is given from Standard Input in the following format. 
$S\ T$

Constraints

  • $1\leq |T|\leq |S| \leq 10^5$
  • $|T|\leq 10^3$
  • $S,T$ both consist of lowercase English letters

Output

Print a newline at the end.

Sample

Sample 1
Input
aab ab
Output
4

For example, when $i=0$, $u=$(empty). The number of occurrences of ab among the substrings of $u$ is $0$.

Also, when $i=5$, $u=$ab. The number of occurrences of ab among the substrings of $u$ is $1$.

Continuing in this way, the answer is $0+0+0+0+0+1+1+2=4$.

Sample 2
Input
abc abd
Output
0

The answer may be $0$.

Sample 3
Input
kazuppa ap
Output
64

The score is so-so, I'd say.

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