꽃 배달

以顶点 $1$ 为根，把花店编号为 $0$ 到 $K-1$。令 $m_v$ 为顶点 $v$ 的子树中花店的位掩码。由下至上按位或合并子节点掩码，可在 $O(N)$ 时间内求出全部 $m_v$。

访问完花店集合 $S$ 后，经过的顶点恰好是从根到 $S$ 中各花店的路径并集。因此采摘的花朵总数为 $F(S)=\sum_{v:(m_v\mathbin{\&}S)\ne0}a_v$。此时已经卖出 朵花，所以前缀集合 合法当且仅当 。

定义 $b[T]=\sum_{v:m_v=T}a_v$、。利用 SOS DP 求得 ，则有 。其中异或用于求出 在 位范围内的补集。

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