27305번 - Fuzzing Mutant Test

고려대학교 사이버국방학과에 다니고 있는 동우(가명)는 지난 학기에 김승주 교수님의 보안공학개론 수업에서 퍼징(Fuzzing)과 Mutant에 대해 배웠다. 퍼징이란 어떤 프로그램에 입력 데이터를 계속 바꿔가면서 넣어 그 데이터로부터 도출되는 결과가 올바른지, 오류가 발생하지는 않는지 등을 판단하는 테스트 기법이다. 그리고, Mutant란 코드를 일부만 변형시켰을 때 프로그램의 결과가 얼마나 변화하는지를 확인하는 방법이다. 그런데, 이 Mutant를 코드에 적용하는 것이 아니라 입력 테스트 케이스에 적용한다면 퍼징을 진행할 수 있게 된다. 이 사실에 깊은 감명을 받은 동우는 자신의 프로그램에 Mutant를 통한 퍼징 기법을 적용해보고자 한다.

비상한 두뇌를 가진 동우는 어떤 입력 데이터가 주어지면 그에 대한 Mutant를 만들어 그다음 입력 데이터를 생성하는 Mutant 생성 알고리즘을 개발해냈다. 즉, 첫 번째로 주어질 입력 데이터만 있으면 그 이후의 데이터들은 일정한 패턴을 통해 자동적으로 생성할 수 있는 것이다. 이제 이렇게 생성된 데이터들을 차례대로 동우의 프로그램에 넣어 그 결과들을 분석하려 한다. 단, 프로그램의 가능한 출력 결과는 $0$과 $1$만 존재한다.

비상한 두뇌를 가진 동우는 자신의 알고리즘이 얼마나 효율적인지 평가하는 방법 또한 개발해냈는데, 그 방법은 다음과 같다. 만약 현재 데이터의 출력 결과가 직전 데이터의 출력 결과와 같으면 현재 데이터를 직전 데이터와 같은 그룹으로 포함시키고, 다른 출력이 나오면 현재 데이터부터 새로운 그룹으로 간주하기로 한다. 즉, 첫 번째 데이터에 대해 하나의 그룹으로 시작한 뒤 순차적으로 다음 입력을 검사해 연속된 같은 출력을 하나의 그룹으로 묶은 것이다. 동우의 생각대로라면 최종적인 그룹의 개수가 많을수록 출력 결과가 더욱 많이 바뀌는 것이므로 효과적인 Mutant 생성 알고리즘이라 생각해, 그룹의 개수를 그 알고리즘의 점수로 매기기로 했다. 또한, 생성되는 데이터의 유형이 직선형과 고리형의 두 가지 유형으로 분류된다는 사실을 알았다. 직선형이란 새롭게 생성되는 데이터가 기존의 데이터와 무조건 다르게 생성되는 유형으로, 모든 데이터가 다르다는 것이 보장되는 유형이다. 고리형이란 데이터를 순차적으로 생성해 나가다가, 어느 순간 첫 번째 데이터와 동일한 데이터가 등장하여 다시 순환하게 되는 유형이다.

동우는 자신이 만든 알고리즘의 점수를 알았지만, 비교할 표준이 없다는 사실에 낙담했다. 그래서 이에 대한 표준을 알아내기 위해 직선형과 고리형 각각에 대한 분포를 구해내고자 한다. 우선 직선형의 경우 $0$과 $1$이 각각 $n$개, $m$개로 이루어진 모든 문자열에 대해 연속한 같은 숫자끼리 그룹을 만들어 그 개수를 세서 점수를 매긴다. 고리형의 경우 $0$과 $1$이 각각 $n$개, $m$개로 이루어진 문자열을 원형으로 배열해 처음과 끝이 연결되어 있다고 생각해 마찬가지로 그룹을 나누어 그룹의 개수를 세서 점수를 매긴다. 이때, 동우를 도와 두 유형 각각에 대해 점수의 기댓값과 분산을 구해보자.

첫 번째 줄에 테스트케이스의 개수 $T$ ($1 \le T \le 10^5$)가 주어진다.

두 번째 줄부터 한줄에 테스트케이스 하나씩 정수 $n$과 $m$ ($0 \le n, m \le 45\,000$, $1 \le n + m$)이 공백으로 구분해 주어진다.

각 테스트케이스 별로 $0$과 $1$이 각각 $n$개, $m$개로 이루어진 직선형의 문자열에 대한 그룹 개수의 기댓값과 분산, 고리형 문자열에 대한 그룹 개수의 기댓값과 분산을 각각 공백으로 구분해 출력한다.

만약 답이 정수라면 그대로 출력하고, 정수가 아닌 유리수라면 기약분수 ${p\over q}$ ($1 \le p$, $2\le q$이며 $gcd(p,q)=1$)로 약분해 $p$/$q$의 형태로 출력한다.

정답이 유리수임을 증명할 수 있다.