Reading KakaoTalk

각 사람 $p$가 마지막으로 작성한 메시지의 번호를

$$L_p=\max(\{i\mid A_i=p\}\cup\{0\})$$

라고 하자. 작성자 조건은 $C_p\ge L_p$와 같다.

편의를 위해 $B_0=N$, $B_{M+1}=0$으로 둔다. 정확히 번 메시지까지 읽은 사람의 수를 라고 하면

$$D_k=B_k-B_{k+1}\qquad(0\le k\le M)$$

이다. 입력에서 $B$가 비증가 수열임이 보장되므로 모든 $D_k$는 음이 아닌 정수이다.

$E_k$를 $L_p\le k$인 사람의 수라고 하자. $C_p=k$가 되려면 반드시 여야 한다.

$k=0,1,\cdots,M$ 순서로 $C_p=k$인 사람을 정한다. $$보다 작은 값을 이미 받은 사람은 정확히

$$N-B_k$$

명이다. 이들은 모두 $L_p\le k$를 만족한다. 따라서 아직 값을 받지 않았고 $C_p=k$가 될 수 있는 사람은

$$E_k-(N-B_k)$$

명이다.

이 중 정확히 $D_k$명을 고르면 된다. 따라서 답은

$$\prod_{k=0}^{M}\binom{E_k-(N-B_k)}{D_k}$$

이다. 문제에서 유효한 수열이 하나 이상 존재한다고 보장하므로 모든 단계의 선택은 가능하다. 구현에서는 조합의 위쪽 값이 $D_k$보다 작거나 음수인지 확인해도 된다.

각 사람의 $L_p$를 구한 뒤, $L_p$의 빈도에 대한 누적합으로 모든 $E_k$를 구할 수 있다. 팩토리얼과 역팩토리얼을 전처리하면 각 조합을 에 계산할 수 있다.

시간 복잡도는 $O(N+M)$이고, 메모리 복잡도는 $O(N+M)$이다.