말랑말랑 계산 직관 트레이닝

$q$번 질의의 값을 $N,M,a,b$라 하자.

$M$번 누적합한 뒤의 마지막 항에서 원래 항 $B^{(0)}_i$가 더해지는 횟수는

$$\binom{N-i+M-1}{M-1}$$

이다. 따라서 답은 다음과 같다.

$$\sum_{i=1}^{N} (a i+b)\binom{N-i+M-1}{M-1}$$

조합 항등식

$$\sum_{i=1}^{N}\binom{N-i+M-1}{M-1}=\binom{N+M-1}{M}$$

와

$$\sum_{i=1}^{N} i\binom{N-i+M-1}{M-1}=\binom{N+M}{M+1}$$

를 사용하면 답은

$$a\binom{N+M}{M+1}+b\binom{N+M-1}{M}$$

이다.

모든 질의에서 필요한 조합의 위쪽 값은 최대 $N+M \leq 400\ 000$이다. $P=1\ 000\ 000\ 007$은 소수이므로 팩토리얼과 역팩토리얼을 $400\ 000$까지 전처리하면 각 질의를 $O(1)$에 처리할 수 있다.

전체 시간 복잡도는 $O(Q+400\ 000)$이다.

Solution written by GPT5.5