XSY4366 Stardust的连接

将原图转化为一张 $n\times \lfloor\frac{n}{B}\rfloor$ 的网格图，原图上一点 $i$ 有 $i\rightarrow (\frac{i}{B},i\times A^{-1}\bmod B)$

容易发现有三种边 $(x,y)\rightarrow (x+1,y)$，$(x,y)\rightarrow (x,y+1)$ 和 $(x,y)\rightarrow (x+1,y+1)$
其中 $y=B-1$ 时后两种边会连回第一列

考虑轮廓线DP，可以按行或按列DP，按行的复杂度为 $\Theta(n2^B)$
由于有从最后一列连回第一列的边，按列需要枚举最后一列的状态分别DP，复杂度为 $\Theta(n4^{\lfloor\frac{n}{B}\rfloor})$

两种取较小值得到 $\mathcal{O}(n2^{\sqrt{2n}})$

事实上按行DP可以换成从小到大枚举 $i$，状压 $i-B...i-1$ 的匹配状态