꽃 배달

트리를 $1$번 정점에 뿌리내리고, 꽃집에 $0$부터 $K-1$까지 번호를 붙인다. 정점 $v$의 서브트리 안에 있는 꽃집의 비트마스크를 $m_v$라고 하자. 자식의 마스크를 OR하여 $O(N)$에 계산한다.

꽃집 집합 $S$를 방문한 후 지나간 정점은, $1$번 정점에서 $S$의 각 꽃집까지 가는 경로의 합집합과 정확히 같다. 따라서 딴 꽃의 총수는 $F(S)=\sum_{v:(m_v\mathbin{\&}S)\ne0}a_v$이다. 개를 이미 팔았으므로, 접두 집합 가 유효할 필요충분조건은 이다.

$b[T]=\sum_{v:m_v=T}a_v$ 및 라 하자. SOS DP로 를 계산한다. 그러면 이다. 여기서 XOR를 이용해 의 보수 마스크를 구했다.

$dp[S]$를 정확히 $S$의 꽃집을 성공적으로 방문한 순서의 수라 하자. $dp[0]=1$이고, $S\ne0$에 대해 다음과 같다.

$$dp[S]=\begin{cases}0,&F(S)<|S|,\\\sum_{i\in S}dp[S\setminus\{i\}],&F(S)\ge |S|.\end{cases}$$

마지막 꽃집 $i$별로 경우를 나눈 것이다. 모든 덧셈은 $998\,244\,353$으로 나눈 나머지로 계산하고, 답은 $dp[(1\ll K)-1]$이다.

시간 복잡도는 $O(N+K2^K)$, 공간 복잡도는 $O(N+2^K)$이다. 꽃의 총수는 이하이므로 64비트 정수로 충분하다.

Solution written by GPT6