做题记录 25.10.18

· · 个人记录

\textcolor{black}\odot AT_ddcc2017_final_d なめらかな木

令 f_{i,u,v,S} 表示数字 1\sim i 中 i-1 填在 u，i 填在 v，子集 S 已经填好的方案数

转移为

[x\notin S][N(u)\subset (S\cup \{x\})]f_{i,u,v,S}\to f_{i+1,v,x,S\cup\{x\}}

答案为 \sum_u\sum_v f_{n,u,v,U}

只存储有效状态，显然合法时所有点度数 \le 4，因此从 u 和 v 处分割开至多有 7 块，每块内同时选或同时不选，状态数量为 O(n^22^7)（由于 i=|S|，因此合法的 u,v 对应不超过 2^7 种 (S,i)），复杂度 O(n^32^7)

代码

参考