[백준 13172번] 파이썬 - ∑ (시그마)

http://wwww.acmicpc.net/problem/13172

 

 

# 조건

• 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)
• 소수 모듈러에서만 성립하는 페르마의 소정리에 의해 b^(X - 1) ≡ 1 (mod X)가 성립하기에, b^(X - 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일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.

 

# 접근 방법

• 우선 모듈러 곱셈 역원에 대해 알아보아야 한다.
• 참고 - https://cheon2308.tistory.com/entry/Algorithm-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EB%AA%A8%EB%93%88%EB%9F%AC-%EA%B3%B1%EC%85%88-%EC%97%AD%EC%9B%90
• 문제가 너무 길고 어려워 이해하는 것부터 어려웠다.
• 쉽게 요약 하면
• b^(X-2) = b^(-1)
• a b^(-1) = a b^(x-2) % 1,000,000,007 이므로
• a * b^(1,000,000,005) % 1,000,000,007 를 시간 안에 푸는 문제이다.
• 따라서, 분할 정복을 이용하여 1000000005 제곱을 구해주는 문제!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
a = 1000000007  
  
def modular(num, exp):  
    if exp == 1:  
        return num % a  
  
    elif exp % 2 == 0:  
        return modular(num, exp //2) ** 2 % a  
  
    else:  
        return num * modular(num, exp-1) % a  
  
M = int(input())  
result = 0  
dice = [[*map(int, input().split())] for _ in range(M)]  
for i, j in dice:  
    result += j * modular(i, a-2) % a  
  
print(result % a)