꽃 배달

頂点 $1$ を根とし、花屋に $0$ から $K-1$ まで番号を付ける。頂点 $v$ の部分木内の花屋のビットマスクを $m_v$ とする。子のマスクを親に OR して $O(N)$ 時間で求める。

集合 $S$ の花屋を訪問した後、通過した頂点は根から $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$ について

$$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