[R22F]子序列计数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定两个字符串 $s$ 和 $t$。考虑字符串 $s$ 的所有不同的重排列（即包含所有字符、考虑重复性的所有可能的排列方式）。对于每一个 $s$ 的重排列，统计其中 $t$ 作为子序列的个数。请求出所有这些统计个数之和。

由于结果可能非常大，请输出最终答案对 $998244353$ 取模后的值。

• 一个字符串的重排列是通过重新排列其字符顺序得到的新字符串（例如，字符串 aab 的重排列包括 aab, aba, baa）。

• 子序列是指从排列中删除某些字符（也可以不删除）而不改变剩余字符的相对顺序形成的新序列。例如，在字符串 aab 中，子序列 ab 可以通过选择第一个和第二个字符，或者第一个和第三个字符，得到两次出现。

格式

输入格式

第一行包含一个字符串 $s$。

第二行包含一个字符串 $t$。

输出格式

输出一个整数，表示满足条件的无序对的数量。

样例

样例输入 #1

aabb
ab

样例输出 #1

12

样例解释 #1

字符串 aabb 的所有重排列共有 6 种：

aabb（出现 4 次）, abab（出现 3 次）, abba（出现 2 次）,

baab（出现 2 次）, baba（出现 1 次）, bbaa（出现 0 次）。

总次数为 $4+3+2+2+1+0=12$。

数据规模

对于 $30\%$ 的数据，$1 \leq |s| \leq 10$。

对于 $50\%$ 的数据，$1 \leq |s| \leq 100$。

对于 $100\%$ 的数据，$1 \leq |s| \leq 500$，$1 \leq |t| \leq 3$，字符串 $s$ 和 $t$ 仅由小写字母组成。