三叉求和 题解

· · 题解

假设路径经过的每一条边依次为从上一个点 x 走到 3x+b_i+1，将经过的 a_i（去掉 a_0）和 b_i 依次写成序列，容易发现：

b_i=\sum_{j=1}^i 3^{i-j}a_{j}

现在要 \sum b_i=k，就是

\sum_{i=1}^d \sum_{j=1}^i 3^{i-j}a_{j}=k \sum_{i=0}^{d-1}3^i\times\sum_{j=1}^{d-i} a_j=k

记 a 的前缀和为 s，即有

\sum_{i=0}^{d-1}3^is_{d-i}

但是 a 和 s 都未知，需要计数方案，考虑 dp。

记 f_{i,j,k} 表示当前 dp 到 i，s_{d-i}=j，i-1 向当前位进位 k 的方案数，注意到 s_{d-i+1}-s_{d-i}\in\{0,1,2\} 所以一个状态的后继状态个数为 O(1)。

状态 O(n^3)，转移 O(1)，时间复杂度 O(n^3)。

注意到对于一组 (i,j)，满足 f_{i,j,k} 非零的 k 的数量是 O(1) 个，所以状态数其实是 O(n^2) 的，拿 umap 或者 vector 存一下就行了，时间 O(n^2)。