A. Splits $\!$
숫자 $n$이 주어진다. $n$의 영혼은 증가하지않는 양의 정수의 수열을 의미하고, 이 수열의 합은 $n$이다. 영혼의 무게는 영혼의 가장 첫 번째 원소(즉, 가장 큰 수)와 같은 원소의 개수를 의미한다. 이때, $n$의 영혼의 무게의 개수를 구하는 문제다.
문제를 딱 보고 이거 너무 어려운데? 생각했는데 예제를 보니 간단하게 풀린다는걸 알 수 있었다. 모든 수 $n$에 대해 무게가 1인 영혼은 무조건 존재한다. $[n]$의 수열이 있으니까. 무게가 2인 영혼은? $[n / 2, n / 2]$ 또는 $[n / 2, n / 2, 1]$이 있으면 있을 것이다. 무게 3.. 4.. 모두 마찬가지로 $[n / k .... n / k, 1,1...1,1,1]$로 만들 수 있다.(1은 $n % k$개) 근데 $k$가 $n / 2$보다 크게 될 경우는 $n / k$가 1이 되므로 더 이상 $k$를 증가시킬 수 없다. 따라서, $[1, n / 2 + 1]$개(n / 2 + 1번째 녀석은 무게가 $n$인 영혼을 만든다.) 즉, $n / 2 + 1$개의 무게의 영혼이 있다.
$A$번 치고 풀이가 긴데 예제의 NOTE만 딱 보면 바로 아 이거네 하고 알 수 있다.
Vasya에게 문자가 $n$개가 온다. 각 문자는 $t_i$분에 오며 처음에 $A$의 가치를 갖고 있고, 문자를 받은 이후 문자를 확인할 때 까지 1분당 $B$원이 감소한다. 또한, 각 분당 확인하지않은 문자의 개수$ * C$만큼 Vasya에게 돈이 입금된다. 각 문자를 확인했을 때 당시 문자의 가치만큼 Vasya에게 입금되며, $T$분 시점에 Vasya는 모든 문자를 확인해야만 한다. Vasya가 얻을 수 있는 돈의 최대값을 구하는 문제다.
쓸때없이 문제를 복잡하게 설명해서 간단한 문제를 어려운듯이 만들었다. 문자를 받은 뒤 확인하지 않고 놔둘 때 마다 $B$원이 감소하며, $C$ * (확인하지 않은 문자의 총 개수)원이 입금된다. 즉, 각 확인하지 않은 문자마다 $(C - B$원이 입금된다는 소리와 같다. 따라서, $C > B$이면 문자를 끝까지(T초) 확인하지 않고 삭혀두는게 이득이다. $C < B$이면 문자가 오자마자 확인해야 이득이다.
즉, $C > B$이면 $A * n + (C - B) * t_i$가 정답이고, $C < B$이면 $A * n$이 정답이다.
길이 $n + 1$짜리 수열 $s$가 있다. 이 수열은 $k$개 마다 반복되는 수열이며, 수열의 각 값은 -1이거나 1이다. $a$와 $b$ 그리고 길이가 $k$인 수열 $s$의 일부분이 주어진다. 이때 $(\sum_{i = 0}^n s_ia^{n - i}b^i) MOD (10^9 + 9)$를 구하는 문제다.
수열이 $k$마다 반복된다는 점에 착안해보자. 먼저 구해야하는 합의 처음 $k$개는 $(\sum_{i = 0}^{k-1} s_ia^{n - i}b^i)$ 이다. 이 값을 $a_0$라 하자. 구해야하는 합은 값이 $(n + 1) / k$번 반복되는데, 한번 반복 될 때 마다 $({b \over a})^k$만큼 $a_0$이 커진다는 것을 알 수 있다. 그리고 이 증가폭을 $r$이라 해보자.
이제 고등학교 교육과정에서 그렇게 나왔던 초기값이 $a_0$이고 증가값이 $r$인 등비수열의 형태가 보임을 알 수 있다. 즉, 우리가 구하는 값은 $\sum_{i = 0}^{(n+1)/k} a_0*r^i$이다. $(n+1)/k$를 $t$라고 하면 우리가 구하는 값은 등비수열의 합 공식에 의해 $(a_0*(r^t - 1)) \over (r - 1)$임을 알 수 있다.
여기까지보면 간단한 문제다. 문제는 이제 MOD연산이 끼어있다는 점이다. 합과 곱에 대한 MOD연산은 MOD연산을 한뒤 합과 곱을 하고 다시 MOD를 취하면 된다. 차는 MOD연산을 할 값을 더한 뒤 MOD연산을 해주면 된다. 문제는 나누기이다. boj에 잘 정리되어 있는데, $(A / B) \% x$ = $(A * (B^{(x - 2)} \% x) \% x)$와 같다. 이걸이용해서 풀어주면 된다.
또, 예외가 하나 있는데 $r$이 1일때 이다. 예외처리를 안 해주면 분모가 0이 되어 큰일난다.
처음에 $n$이 큰 줄 모르고 naive하게 돌리다가 tle맞고 나누기에도 그냥 MOD 하고 나누기 하는 바람에 틀렸다. 나누기에 MOD연산은 다른 방법을 써야한다는 얘기를 듣고 부랴부랴 찾아서 해봤는데 계속 틀리길래 보니 $r$이 1일때 예외처리를 안 해줬다. 그리고 MOD연산을 많이 해야하면 합,차,곱,나누기를 수행해주는 함수를 따로 만들어서 함수로 넘겨버리자. 이렇게 해야 MOD연산을 깜박하지않는다.
=수정중=
