[SWEA 26009] 곱의 합 [Python]

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

요약

• 등차수열 합 공식을 이용해 모든 조합에 대한 곱을 구하자.
• 결과는 998,244,353으로 나눈 나머지로 출력한다.

---

풀이 과정

수식 변형

구해야 하는 모든 i, j, k 조합에 대해 i * j * k를 구헤야 한다.

$(1+2+⋯+a)×(1+2+⋯+b)×(1+2+⋯+c)$

하지만 반복 횟수가 최대 $10^{27}$으로 시간 초과가 발생한다. 등차수열의 합 공식을 활용한 빠른 계산이 가능하다.

$1 + 2 + \cdots + a = \frac{a(a+1)}{2}$

$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} (i×j×k)=\frac{a(a+1)}{2}×\frac{b(b+1)}{2}×\frac{c(c+1)}{2}$

def solve():
    sum_a = A * (A + 1) // 2
    sum_b = B * (B + 1) // 2
    sum_c = C * (C + 1) // 2
    return (sum_a * (sum_b * sum_c) % MOD) % MOD

변형한 수식에 따라 세 합을 곱한 뒤 문제에서 요구한 MOD값으로 나눈 나머지를 출력하자.

 

성능 분석

• 시간 복잡도: $O(1)$
• 제출결과: Pass/ 57ms / 49,536kb

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/SW%20Expert%20Academy/D3/26009.py

problem-solving/SW Expert Academy/D3/26009.py at main · rogi-rogi/problem-solving