빠르게 계산하기

길이가 $N$, 각 항의 값이 $1$ 이상 $M$ 이하의 정수인 수열의 개수를 세는 상황을 생각해 보자.

먼저, 모든 항이 같은 수열은 총 $M$가지이다.

따라서 $2$개 이상의 서로 다른 값을 포함하는 수열은 $M^N-M$가지가 존재한다. 이 중 최솟값의 위치를 $A_i$, 최댓값의 위치를 $A_j$라고 하자. 만약 최댓값 또는 최솟값이 여러 위치에 존재한다면 그 중 가장 번호가 작은 것으로 가정한다.

이때 $i<j$인 경우와 $i>j$인 경우가 일대일 대응됨을 확인할 수 있다. ($\{A_1, A_2, \dots, A_N\} \leftrightarrow \{M+1-A_1, M+1-A_2, \dots, M+1-A_N\}$)

따라서 $i<j$인 경우는 총 $\frac{M^N-M}{2}$가지이다.

$A_j-A_i=d$인 상황을 생각해 보자. 이 조건을 만족하도록 $A_i, A_j$의 값을 정하는 경우의 수는 $M-d$가지이다.

$p\neq i, p\neq j$인 $A_p$를 정하는 방법의 수는 $p$에 대해 다음과 같다.

• $1\le p< i$ : $A_i<A_p<A_j$, 총 $A_j-A_i-1=d-1$가지
• $i< p< j$ : $A_i\le A_p<A_j$, 총 $A_j-A_i=d$가지
• $j< p\le N$ : $A_i\le A_p\le A_j$, 총 $A_j-A_i+1=d+1$가지

따라서 $i<j$인 수열의 개수는 $\sum_{d=1}^M (M-d)\sum_{1\le i<j\le N} (d-1)^{i-1}d^{j-i-1}(d+1)^{N-j}$가지이며, 이는 구해야 하는 식과 일치한다.

따라서 답은 $\frac{M^N-M}{2}$이며, $O(N)$ 또는 $O(\log N)$의 시간복잡도로 계산할 수 있다.