分数: 6 点
问题陈述
给你两个字符串 S 和 T。 查找至少属于以下之一的子序列的字符串数量 S 和 T,模数 998244353.
这里是一个字符串 A 据说是字符串的子序列 B 当长度 A 至少 1 和 A 可能是由于从其中删除零个或多个字符而导致的 B。例如, atcoder 和 ac 是子序列 atcoder,同时 atcoderr 和 ca 不是。
约束
- 1 \leq \lvert S\rvert, \lvert T\rvert \leq 1000
- S 和 T 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
S T
输出
打印答案。
示例输入 1
abc bca
示例输出 1
10
S= abc 有七个子序列: a, b, c, ab, ac, bc, abc,同时
T= bca 有七个子序列: b, c, a, bc, ba, ca, bca。
因此,我们有十个字符串,它们至少是其中之一的子序列: a, b, c, ab, ac, ba, bc, ca, abc, bca.
示例输入 2
aa aaaaa
示例输出 2
5
寻找的字符串是 a, aa, aaa, aaaa, aaaaa.
示例输入 3
xzyyzxxzyy yzxyzyxzyx
示例输出 3
758