BOJ-7393 "Irrelevant Elements" 풀기

이 문제는 $[a_0,,a_1,,\cdots, a_n]$으로 이루어진 리스트가 있다. 그리고 자기와 그 다음 원소를 더한 값을 원소로 갖는 그 다음 단계의 리스트를 구하고, 구하고, 구하고... 해서 최종적으로 하나의 원소를 가진 리스트의 원소를 구한다. 그 원소를 법 $m$에 모듈로 연산한다고 하자.

하지만, 이 때 구한 값을 $f(a_1, \cdots, a_n)$이라고 하면 실제로 이 값이 $a_i$와 아무런 관련도 없을 수 있다. 그런 값을 모두 구하는 것이 문제이다.

우리는 단계 $k$의 길이가 $n$인 각 원소의 계수의 개수를 원소로 갖는 벡터를 정의하여 처음에는 $[1, 1, \cdots, 1]$, 그 다음에는 $[1, 2, \cdots, 2, 1]$ 이렇게 하여 최종적인 단계의 계수는 다음과 같다: $$\left[ \binom{n-1}{0}, \binom{n-1}{1}, \cdots, \binom{n-1}{n-1} \right]$$

우리는 각 계수의 모듈로 $m$이 0인지를 확인하면 된다.

처음 시도

$n$이 최대 10만이므로 $O(n^2)$인 파스칼의 삼각형을 이용한 방법은 안된다. 따라서 그다음인 factorial inverse 방법을 생각해봤다.

하지만 $m$이 충분히 크지 않을 수 있다는 점이 문제였다. 예를 들어 $n \geq m$이라면 $n! \mod m$은 항상 $0$이 나오는 문제가 있다. 이는 inverse를 이용한 계산을 불가능하게 하는 문제가 있다.

풀이

르장드르 공식을 이용했다.

르장드르 공식은 다음을 의미한다.

소수 $p$가 주어졌을 때, 양의 정수 $n$에 대해 p진 값매김(p-adic valuation) $\nu_p$는 다음과 같다: $$\nu_p(n!) = \sum_{i=1}^{\infty}{\left\lfloor \frac{n}{p^i} \right\rfloor}$$

르장드르 공식을 이용한 p-진 값매김을 구하는 것의 시간 복잡도는 $O(\log_p n)$이다.

따라서 $m$을 소인수 분해하여 나온 $m = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k} $가 있다고 하자. 그리고 $\binom{n}{i}$의 $p_1$ 부터 $p_k$까지의 값매김을 구한 다음에 모두 $m$보다 크거나 같은지 확인하여 나누어 떨어짐을 구하면 된다.

전체 시간 복잡도는 $O(k\log_p n)$. 이때 $k\leq 9$임은 쉽게 보일 수 있어서 무시할 수 있다. 따라서 전체 시간 복잡도는 $O(\log_p n)$이다.

다른 풀이

르장드르 공식 대신에 누적합을 이용하면 된다.