시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 9 | 5 | 5 | 55.556% |
A string consisting of letters 'A
', 'B
', 'C
' is good if every two adjacent letters are different.
A pair of two good strings $(s, t)$ of length $2n + 1$ is awesome if the length of their longest common subsequence is exactly $n$.
You are given two strings, $s$ and $t$, consisting of letters 'A
', 'B
', 'C
' and question marks ('?
'). Find the number of ways to replace each '?
' with one of 'A
', 'B
', 'C
', so that the pair ($s$, $t$) is awesome, modulo $998\,244\,353$.
The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$).
The second line contains a string $s$ of length $2n+1$ consisting of characters 'A
', 'B
', 'C
', '?
'.
The third line contains a string $t$ of length $2n+1$ consisting of characters 'A
', 'B
', 'C
', '?
'.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
For each test case, output the number of ways to replace each '?
' with one of 'A
', 'B
', 'C
' so that the pair $(s, t)$ is awesome, modulo $998\,244\,353$.
5 1 ABA CBC 1 A?A C?C 1 ??? ??? 2 AA??? ????B 3 ?A?B?A? ???????
1 3 24 0 2
In the first test case, pair (ABA
, CBC
) is awesome.
In the second test case, there are $3$ ways to replace question marks to get an awesome pair: (ABA
, CBC
), (ACA
, CBC
), (ABA
, CAC
).