12996. Acka

Acka는 ``악어``라고 읽는다. 모 랭커분의 닉네임이다.

12996번: Acka

---

세 사람이 불러야 하는 곡의 개수 $a$, $b$, $c$가 주어질 때, 만들 수 있는 앨범의 개수를 구해 보자. 뭔가 고등학교 확통 느낌이 나는 문제이다.

 

일단 특이 케이스부터 먼저 살펴보자. $a+b+c<s$라면 앨범을 만들 수 없다. 또, $a+b+c=s$라면 그냥 중복순열을 계산하면 된다. 이제 일반적인 경우를 생각해 보자. 구하는 정답을 $solve(s)$라고 하겠다.

 

각자 불러야 하는 개수만큼 곡을 고르는 경우의 수는 $\left(\begin{array}{c}s\\ a\end{array}\right) \times \left(\begin{array}{c}s\\ b\end{array}\right) \times  \left(\begin{array}{c}s\\ c\end{array}\right)$이다. 그런데 이렇게 하면 선택되지 않는 곡이 있을 수 있으므로, 적어도 하나의 곡이 선택되지 않는 경우를 빼면 된다.

 

그러나 몇몇 곡을 선택하지 않는다고 해도, 최소한 $\max(a,~b,~c)$개는 선택해야 한다. 곡 개수가 더 적어지면 한 사람이 같은 곡을 두 번 선택해야 하는 상황이 되기 때문이다.

 

따라서 적어도 하나의 곡이 선택되지 않을 때, 선택할 수 있는 곡의 범위는 $[max(a,~b,~c),~s)$이다. 이제 곡의 일부만을 골랐을 때 앨범의 개수를 계산하면 된다. 이 값은 ``일부 곡을 선택하는 경우의 수``와 ``그 때의 정답``을 곱한 값과 같다. ``일부 곡을 선택하는 경우의 수``는 그냥 이항계수이고, ``그 때의 정답``은 $solve$의 재귀로 구할 수 있다.

 

따라서 $\forall ~ i \in [max(a,~b,~c),~s)$에 대해 $\left(\begin{array}{c}s\\ i\end{array}\right) \times solve(i)$를 구하고, 각각의 값을 정답에서 빼면 된다.

 

모듈러 연산이 있으므로 계산식에 주의하자. 이항계수를 구할 일이 많으므로 dp로 미리 계산해 두면 좋다.

---

생각보다 시간을 많이 썼다. 이 정도는 1시간 안에 풀어야 하는데..