23127번 - Little LCS
문자 'A', 'B', 'C'로 이루어진 문자열이 다음 조건을 만족하면 좋은 문자열이라고 합니다.
- 모든 인접한 두 문자가 다르다.
길이가 $2n+1$인 두 좋은 문자열 $s$, $t$의 쌍 $(s, t)$이 다음 조건을 만족하면 멋진 쌍이라고 한다.
- 두 문자열의 최장 공통 부분 수열(LCS)의 길이가 정확히 $n$이다.
당신은 두 개의 문자열 $s$, $t$가 주어지며, 각 문자열은 'A', 'B', 'C', '?'로 이루어져 있다. 여기서 각 '?'를 'A', 'B', 'C' 중 하나로 치환하는 모든 경우의 수를 구해야 한다. 단, 치환 후 $(s, t)$는 멋진 쌍이 되어야 한다.
치환 방법을 $998\ 244\ 353$으로 나눈 나머지를 출력하라.
[입력]
첫 번째 줄에 테스트케이스의 개수 $t$가 주어진다. 각 테스트케이스는 다음과 같이 주어진다.
첫 번째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^6$)
두 번째 줄에 길이 $2n+1$인 문자열 $s$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.
세 번째 줄에 길이 $2n+1$인 문자열 $t$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.
모든 테스트케이스에서 $n$의 총함이 $10^6$을 넘지 않음이 보장된다.
[출력]
각 테스트케이스마다 한 줄에 정수 하나를 출력한다. 이 값은 모든 '?'를 치환하는 방법의 수이며, $(s, t)$가 멋진 쌍이 되도록 하는 경우의 수를 $998\ 244\ 353$으로 나눈 나머지이다.
[힌트]
첫 번째 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC)이다.두 번쨰 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC), (ACA, CBC), (ABA, CBC)이다.
댓글을 작성하려면 로그인해야 합니다.
realpsdoingdamyoo 1년 전
문자 'A', 'B', 'C'로 이루어진 문자열이 다음 조건을 만족하면 좋은 문자열이라고 합니다.
- 모든 인접한 두 문자가 다르다.
길이가 $2n+1$인 두 좋은 문자열 $s$, $t$의 쌍 $(s, t)$이 다음 조건을 만족하면 멋진 쌍이라고 한다.
- 두 문자열의 최장 공통 부분 수열(LCS)의 길이가 정확히 $n$이다.
당신은 두 개의 문자열 $s$, $t$가 주어지며, 각 문자열은 'A', 'B', 'C', '?'로 이루어져 있다. 여기서 각 '?'를 'A', 'B', 'C' 중 하나로 치환하는 모든 경우의 수를 구해야 한다. 단, 치환 후 $(s, t)$는 멋진 쌍이 되어야 한다.
치환 방법을 $998\ 244\ 353$으로 나눈 나머지를 출력하라.
[입력]
첫 번째 줄에 테스트케이스의 개수 $t$가 주어진다. 각 테스트케이스는 다음과 같이 주어진다.
첫 번째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^6$)
두 번째 줄에 길이 $2n+1$인 문자열 $s$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.
세 번째 줄에 길이 $2n+1$인 문자열 $t$가 주어진다. $s$는 'A', 'B', 'C', '?'로 이루어져 있다.
모든 테스트케이스에서 $n$의 총함이 $10^6$을 넘지 않음이 보장된다.
[출력]
각 테스트케이스마다 한 줄에 정수 하나를 출력한다. 이 값은 모든 '?'를 치환하는 방법의 수이며, $(s, t)$가 멋진 쌍이 되도록 하는 경우의 수를 $998\ 244\ 353$으로 나눈 나머지이다.
[힌트]
첫 번째 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC)이다.
두 번쨰 테스트 케이스에서, 멋진 쌍으로 가능한 것은 (ABA, CBC), (ACA, CBC), (ABA, CBC)이다.