Σ

solved_ac[Class4][시그마](https://www.acmicpc.net/problem/13172)

문제

실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.

이 문제를 조금 확장해서, "N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은 과연 몇일까?"라는 문제가 주어졌다고 하자. 위의 예시에 대한 답을 소수로 출력한다면 2.33333333...일텐데, 무한한 자릿수를 모두 출력할 수는 없으니 적당히 끊어서 출력할 것이고, 이 끊긴 소수를 채점 프로그램이 다시 입력받아서 정답과 비교한다고 하면 결과가 얼마나 부정확할 것인가? 그렇기에 답을 정확히 판별하기 위해 출력하고자 하는 분수를 기약분수로 만들어 분모와 분자를 직접 출력하도록 했던 시기가 있었다.

이제 문제를 조금 더 확장하여, M개의 주사위가 있어서 이 중 i번째 주사위가 Ni면체 주사위이고 모든 면에 적힌 수를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 X의 기댓값을 E(X)로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 X, Y에 대해 E(X + Y) = E(X) + E(Y)가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다.

S1/N1 + S2/N2 + ... + SM/NM

즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다. 이 답을 정확하게 출력하기 위해, 모든 분수(여기서는 각 주사위의 기댓값)를 통분한다고 생각해보자. 이 분수의 분모와 분자의 값이 어떤 범위까지 치솟게 될 것인가? 즉, 분모와 분자를 모두 저장하고 있게 되면, 두 분수의 합을 구할 때 분모와 분자를 적정한 범위 내에서 계산해낼 수 없다는 문제에 부딪히게 된다. "그렇다면 분모와 분자를 어떤 모듈러 상에서 가지고 있으면 되지 않을까?"라고 생각할 수 있지만, 그러면 분모와 분자를 약분할 수가 없게 된다. 그렇기에, 분수를 다음과 같이 모듈러 상에서 하나의 정수로 가지고 있는 방법을 채택하게 되었다.

어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 a × b-1 mod X (X는 소수)으로 대신 계산하도록 한다. 여기서 b-1은 b의 모듈러 곱셈에 대한 역원이다.

b의 모듈러 곱셈에 대한 역원 b-1은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다.

b-1 × b ≡ 1(mod X)

소수 모듈러에서만 성립하는 페르마의 소정리에 의해 bX - 1 ≡ 1 (mod X)가 성립하기에, bX - 2 ≡ b-1 (mod X) 역시 성립함을 알 수 있다.

이해를 돕기 위해 X를 11로 두고 Q = 7/3 을 계산해보자. 3-1 ≡ 4 (mod 11)이므로, Q ≡ 7 × 4 ≡ 6 (mod 11)이다. 이 Q에 3을 곱한 다음 11로 나눈 나머지를 구해 보면 7이 나오므로, 6이라는 정수가 7/3을 적절히 저장하고 있다는 것을 알 수 있다.

분수(유리수)를 이와 같은 방식으로 나타낸다면, 두 분수의 덧셈, 뺄셈, 곱셈은 mod X에서 두 정수를 가지고 계산하듯이 처리하고, 나눗셈은 나누는 분수의 곱셈에 대한 역원을 구한 후 그 역원을 mod X에서 곱하는 것으로 처리한다면, 분수를 정확히 출력하기 위해 통분을 하거나 기약분수로 만드는 골치아픈 일을 할 필요가 없어진다!

그러나 이 방법에도 문제가 있는 것은 마찬가지이다. 앞의 예에서 7/3을 6으로 저장했지만, 그냥 6/1도 6으로 저장할 것이다. 즉 서로 다른 두 분수도 모듈러 상에서 같은 정수로 저장하여, 정확한 판별을 한다는 우리의 목적에 부합하지 않는 것이다. 또다른 문제로는, 분모가 소인수로 X를 가질 때에는 역원을 계산할 수 없어서 모듈러로 나타낼 수가 없다는 점이 있다. 이러한 문제를 해결하기 위해 모듈러를 1,000,000,007와 같은 큰 소수로 하는데, 이를 통해 서로 다른 두 분수가 같은 정수로 나타나게 되는 확률을 낮추고, 분모가 가질 수 있는 소인수의 범위를 늘리는 효과를 볼 수 있다. 그는 이런 방식이 그래도 가장 정확한 방식이라고 생각하게 되었다.

이제 이 방식으로 M 개의 주사위가 있고, i번째 주사위가 Ni면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.

입력

첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.

다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.

출력

모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다

예제 입력 1

1
3 7

예제 출력 1

333333338

힌트

모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.

사용 알고리즘

[분할정복 알고리즘]

이 문제에서 다양한 알고리즘이 사용되지만 그 중 핵심은 분할정복 알고리즘이라고 생각한다.

분할정복 사용이유

거듭제곱을 그냥 하면 되지 굳이 왜 분할정복을 사용하는가? 정답은 시간복잡도 때문이다.

a의 n승을 생각해보았을 때, 냅다 n번 곱하면 O(N)의 시간복잡도이다. 그러나 분할정복을 이용하여 거듭제곱을 구하면 O(log N)의 더 효율적인 시간복잡도로 구할 수 있다. 그 이유는 다음과 같다.

과정 설계

우선, 문제를 풀기에 앞서 나는 이 문제의 배경은 이해하지 못 하고 그저 핵심만 간추려서 풀었다. 왜 모듈러 연산을 하는지 그게 어떤 영향을 미치는지에 대하여 설명하는 것 같은데 아무리 읽어도 이해가 잘 가지 않아 그냥 문제에서 요구하는 조건을 그런가보다 하고 수용하였다. 답을 도출하기까지의 전체적인 outline은 다음과 같다.

Step1

문제에서 원하는 것은 기대값을 기약분수로 표현하여 (a*b^-1) % 100...7 을 구하라는 것이다.

Step2

이 때, b^-1 = b^(x-2) % x 이다.

Step3

x = 100...7 이므로 b^-1 = b^(100...5)이다.

Step4

b^(100...5)를 그냥 구해버리면 시간초과에 걸리기 때문에 우리는 효율적인 분할정복 방식을 이용하여 구할 것이다.

애로사항

분할정복을 떠올리는 것은 쉬웠다. 옛날 백준 문제를 풀었던 기억이 났기에, 거듭제곱의 지수를 보고 단순 거듭제곱이 아니라 시간복잡도를 줄이는 방식으로 가야겠다고 접근하였다. 그러나 Step1을 참고해보면 "기대값을 어떻게 기약분수로 표현할 것인가?"가 관건이었다.

1트

import sys
from fractions import Fraction
input = sys.stdin.readline

# 초기 조건
dice = int(input())
expect = 0
for i in range(dice):
    n,s = map(int,input().split())
    expect += s/n
FLAG = 1000000007

# 기대값을 분수식으로 변환
expect = str(Fraction(expect))
a = expect[0]
b = expect[-1]

# O(log N) 거듭제곱 알고리즘
def power(a,n):
    if n == 0:
        return 1
    
    x = power(a,n//2)

    # x가 짝수
    if n%2 == 0:
        return x*x
    
    # x가 홀수
    else:
        return x*x*a

b_inverse = power(int(b),FLAG-2) % FLAG

# 정답 출력
answer = (int(a)*b_inverse) % FLAG
print(answer)

엉뚱한 결과가 나와버렸다. 그 이유에 대한 나의 추측은 두 가지이다.

오류에 대한 가설1

코드를 보면 기약분수에 대한 표현을 하기 위하여 fraction 모듈을 활용하였다. 그렇게 하여 분자와 분모를 추출하면 되겠다고 생각하였는데 fraction 함수에서 이상한 점을 발견하였다.

from fractions import Fraction

print(Fraction(4/6))

예상하는 결과값: 2/3
실제 결과:

오류에 대한 가설2

예를 들어, (주사위 면 수, 주사위 총합)의 쌍 3개가 다음과 같이 들어왔다고 가정해보자.

(7,3),(8,5),(6,4)

그렇다면 문제에서 요구하는 답은 (7/3+8/5+6/4) % flag이다. 그런데 1트의 코드에서는 공교롭게도 (7/3+8/5+6/4)가 정확하지 않다. 왜냐하면 파이썬은 소수로 표현하여 근사치를 출력해주는 것이니까. 그렇기 때문에 위의 코드에서

expect += s/n

여기서부터 이미 정확한 기약분수가 아닌 소수의 근사치이기 때문에 정확한 값이 아니고 이 때문에 틀린 답이 발생하는 것이 아닐까... 하고 생각해봤다.

2트 (정답 코드)

import sys
import math
input = sys.stdin.readline

# O(log N) 거듭제곱 알고리즘
def power(a,n):
    if n == 0:
        return 1
    
    x = power(a,n//2) % FLAG

    # x가 짝수
    if n%2 == 0:
        return x*x % FLAG
    
    # x가 홀수
    else:
        return x*x*a % FLAG

# 초기 조건
FLAG = 1000000007
sum = 0
dice = int(input())
for i in range(dice):
    n,s = map(int,input().split())
    a = s // math.gcd(n,s)
    b = n // math.gcd(n,s)

    b_inverse = power(b,FLAG-2) % FLAG
    sum += (a*b_inverse) % FLAG
    sum %= FLAG
    
# 정답 출력
answer = sum
print(answer)

최대공약수를 활용하면 기약분수를 표현할 수 있다는 사실을 알게 되었다. 2트의 코드도 마찬가지로 계속 합을 해주므로 가설2 보다는 가설 1쪽이 더 맞는 것 같다. 그리고 예전부터 이해가 안 가는 부분 중 하나는 왜 모든 코드를 FLAG로 나누어 주어야하는지 모르겠다. 저걸 안하면 터미널 창에서조차 시간이 너무 오래걸려 결과값이 출력되지 않는다.