2026년 1월 27일

JAG Summer Camp 2023 Day 2

Sum of Product of Binomial Coefficients

$f(k) = (k + 1)^N$이다. $2^N + 3^N + ... + (K+1)^N \pmod {998244353}$을 계산한다.

Mercurialist

$i$번째 날($0 \le i$)에 처음으로 엘릭서를 마시는 확률을 $f(i)$라고 하자. $j$번째 날($0 \le j < i$)에는 $0$개의 엘릭서, $\max(0, Y - \max(1, i - j + 1 - K) + 1)$개의 수은, $Z$개의 요거트 중에 이전에 마신 $j$개의 병을 제외한 하나를 골라야 한다. $f(i) = \prod_{j < i} \frac{\max(0, \max(0, Y - \max(1, i - j + 1 - K) + 1) + Z - j)}{X + Y + Z - j}$이고 $O(N^2)$에 $\sum {f(i)}$를 계산할 수 있다. 마셔도 괜찮은 수은의 개수가 $0$으로 일정한 구간, $1, 2, \cdots, Y-1$로 증가하는 구간, $Y$로 일정한 구간으로 나누어서 확률이 $0$이 되는 경우, 값이 상한 또는 하한을 넘는 경우를 고려해서 열심히 식을 정리하면 $f(i)$를 팩토리얼을 미리 계산해 두는 것으로 $O(1)$에 구할 수 있고 정답은 $O(N)$에 계산 가능하다.

Umbrella Queries

정$n$각형을 원 위에 놓아보자. 중심각이 $\pi$가 되는 두 점이 존재하는 것과 원주각이 $\frac{\pi}{2}$인 세 점이 존재하는 것은 필요충분조건이다. 따라서 $n$이 홀수일 때는 $0$개, $n$이 짝수일 때는 $\frac{n}{2} \times (n - 2)$개의 쌍이 존재한다.

Gemini Tree (Ver.Jadeite)

흰색 돌이 올라와 있는 정점의 개수를 $A$, 검은색 돌이 올라와 있는 정점의 개수를 $B$라고 하자. 임의의 정점을 루트로 잡고 오일러 투어를 한다. 크기가 $A$인 서브트리의 각 정점에 서브트리의 루트의 번호를 적어놓는다. 이 서브트리의 루트를 리더라고 하자. 리더와 리더의 부모를 연결하는 간선은 지울 수 있는 간선이다. 임의의 간선 $u, v$($u$는 $v$의 부모 정점)가 리더 간선에 얼마나 기여하는지 살펴보자.

정점 $u, v$에 번호가 쓰여 있지 않은 경우.

1. $v$를 루트로 하는 서브트리에 있는 리더 간선에 $v$를 루트로 하는 서브트리에 포함되지 않는 정점의 흰 돌의 개수에 간선의 가중치를 곱해서 더한다.
2. $v$를 루트로 하는 서브트리에 포함되지 않는 리더 간선에 $v$를 루트로 하는 서브트리에 있는 흰 돌의 개수에 간선의 가중치를 곱해서 더한다.

정점 $v$에 번호가 쓰여 있는 경우.

1. $v$의 리더 간선에 $v$의 서브트리에 포함된 검은 돌의 개수에 간선의 가중치를 곱해서 더한다.
2. $v$의 리더의 서브트리에 포함되지 않는 리더 간선에 $v$의 서브트리에 포함된 흰 돌의 개수에 간선의 가중치를 곱해서 더한다.

서브트리의 크기가 $B$인 경우는 대칭적으로 계산할 수 있다. 레이지 세그먼트 트리를 사용하면 한 간선의 가중치가 변할 때 각 리더 간선에 해당하는 트리의 비용을 $O(\log N)$에 갱신할 수 있고, 트리의 최소 비용을 $O(1)$에 얻을 수 있다.