答えは ( \(S\) の部分列となっている文字列の数)+( \(T\) の部分列となっている文字列の数)-( \(S,T\) 両方の部分列となっている文字列の数) で求められます。以下では、空文字列も部分列に含めます。最終的な答えは求まった答えから \(1\) を引けばよいです。

まず、\(S\) の部分列となっている文字列の数を数える方法を考えます。\(S\) の \(i\) 文字目を \(S_i\) で表し、\(S\) の先頭 \(k\) 文字からなる文字列を \(sub(S,k)\) で表します。 \(k=0,1,\ldots,|S|\) について、順に\(sub(S,k)\) の部分列となっている文字列の数を数えます。先頭 \(0\) 文字からなる部分列 (= 空文字列 ) の部分列として数えられるのは 空文字列自身のみで \(sub(S,0)=1\) です。

さて、\(sub(S,k+1)\) の部分列であって、\(sub(S,k)\) の部分列でないようなものについて考えます。まず、最後の文字が\(S_{k+1}\) でなくてはなりません。（そうでなければ、「 \(sub(S,k+1)\) の部分列である」ならば「 \(sub(S,k)\) の部分列である」が成り立ちます。） \(sub(S,k+1)\) の部分列であって最後の文字が\(S_{k+1}\) であるような文字列は、\(sub(S,k)\) の部分列の最後尾に \(S_{k+1}\) を付け加えたものとして書かれることが必要十分条件です。

これらのうち \(sub(S,k)\) の部分列であるものを差し引けばよいです。\(0\leq k'< k\) であって、 \(S_{k'+1}=S_{k+1}\) となる 最大 の \(k'\) を考えます。そのような \(k'\) が存在しなければ、最後の文字が\(S_{k+1}\) であるような文字列はつねに\(sub(S,k)\) の部分列でありません。 \(k'\) が存在した場合について、 もし、\(sub(S,k')\) の部分列の最後尾に \(S_{k+1}(=S_{k'+1})\) を付け加えたものはすでに \(sub(S,k)\) に含まれているため、差し引く必要があります。逆に、\(sub(S,k)\) の部分文字列であって、最後の文字が \(S_{k'+1}\) であるようなものは \(sub(S,k'+1)\) の部分列であるため、上記のもの以外は \(sub(S,k)\) の部分列でないという事ができます。

さて、これらの事から、\(sub(S,k)\) の文字列を \(dp_S[k]\) で表すとすると、\(dp_S[k+1]=dp_S[k]+(dp_S[k]-dp_S[k'])\) で求めることができます。もし\(k'\) が存在しなければ、\(dp_S[k+1]=2\times dp_S[k]\) となります。

さて、各 \(k\) に対する \(k'\) ですが、文字の種類数が \(26\) しかないため、前から順に見ていく事で前計算により \(O(|S|)\) で求めることができます。

よって、\(S\) の部分列であるような文字列の数を求めることができました。\(T\) についても同様です。次に、\(S,T\) 両方の部分列となっている文字列の数を数えることを考えます。

基本的な方針はこれまでに述べてきたものと同様です。

\(dp_{both}[i][j]\) で \(sub(S,i)\) と \(sub(T,j)\) 両方の部分列となっている文字列の数を表します。\(i=0\) または \(j=0\) ならば \(dp[i][j]=1\) となります。そうでないとき、\(sub(S,i+1)\) と \(sub(T,j+1)\) 両方の部分列となっている文字列は次の \(4\) つに分類できます。

• \(sub(S,i)\) の部分列であり、\(sub(T,j)\) の部分列でもあるもの
• \(sub(S,i)\) の部分列であるが、\(sub(T,j)\) の部分列ではないもの
• \(sub(S,i)\) の部分列でないが、\(sub(T,j)\) の部分列ではあるもの
• \(sub(S,i)\) の部分列でも、\(sub(T,j)\) の部分列でもないもの

上の \(3\) 種類の文字列の数の和は \(dp_{both}[i][j+1]+dp_{both}[i+1][j]-dp_{both}[i][j]\) で与えられます。よって、\(4\) 種類目について考えればよいです。\(sub(S,i)\) の部分列でないが \(sub(S,i+1)\) の部分列であるような文字列の最後の文字は\(S_{i+1}\) でなければならず、同様の事が\(T_{j+1}\) についても言えるため、\(S_{i+1}\neq T_{j+1}\) であれば\(4\) 種類目の文字列は存在しません。

\(S_{i+1}= T_{j+1}\) のとき、\(0\leq i'< i\) であって、 \(S_{i'+1}=S_{i+1}\) となる 最大の \(i'\) を取り、および同様に \(T\) に対して \(j'\) を定めます。このとき、今までと同様の議論から \(4\) 番目の文字列の数は \(dp_{both}[i][j]-dp_{both}[i'][j]-dp_{both}[i][j']+dp_{both}[i'][j']\) で与えられます。 \(i'\), \(j'\) が存在しない場合はそれぞれその変数を添字として含んでいる項が \(0\) となり消えるとみなせばよいです。

\(i'\), \(j'\) の求め方はすでに述べた通りで、これによって、\(O(|S||T|)\) で\(S,T\) 両方の部分列となっている文字列を求めることができました。

答えは \(dp_S[|S|]+dp_T[|T|]-dp_{both}[|S|][|T|]-1\) を \(998244353\) で割った余りとなります。 計算量は全体で\(O(|S||T|)\) であるため、よって、十分高速にこの問題を解くことができました。オーバーフローや、余りを取った上で引き算する中で負の数になる可能性がある事に注意してください