2126 . 一個配爾子序列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

DIO
$$\Huge Wryyyyyyyyyyyyyyyyyy$$

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

40.0% (8/20)

Tags

IOIcamp 2019-IOIcamp

Description

對於兩個字串 $S, T$，若可以把 $T$ 的某些字元刪除後得到 $S$，我們就說 $S$ 是 $T$ 的子序列。

給你兩個字串 $A, B$，請你判斷有多少個字串配對 $(S_A, S_B)$，使得 $S_A$ 是 $A$ 的子序列、$S_B$ 是 $B$ 的子序列，而且 $S_A < S_B$。這裡的小於符號指的是字典順序，也就是說 $S_A$ 的字典順序要比 $S_B$ 的字典順序來得前面。

為了方便起見，我們定義空字串也是任意字串的子序列喔！

Input Format

第一行有一個正整數 $T$，代表總共有幾筆測試資料。 每筆測試資料為一行，包含兩個由小寫英文字母組成的字串 $A, B$。

  • $1 \le T \le 50$
  • $1 \le |A|, |B| \le 300$

Output Format

對於每筆測試資料，請輸出一行一個整數，代表符合題目要求的字串配對數除以 $1000000007$ 的餘數。字串配對不應該被重複計算。

Sample Input 1

5
aa ab
zzzzz xxx
abcdefg hijklmno
shik eddy
wangyenjen coquelicot

Sample Output 1

7
3
32640
26
306171

Hints

  • 第一筆測試資料包含 7 個 pair: (空字串, a), (空字串, b), (空字串, ab), (a, ab), (a, b), (aa, ab), (aa, b) 總共 7 個。
  • 第二筆測試資料包含 3 個 pair: (空字串, x), (空字串, xx), (空字串, xxx) 總共 3 個。

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
Submit
Back to Top