LINK:州区划分
把题目中四个条件进行规约 容易想到不合法当前仅当当前状态是一个无向图欧拉回路.
充要条件有两个 联通 每个点度数为偶数.
预处理出所有状态.
然后设\(f_i\)表示组成情况为i的值.
枚举子集转移 可以发现利用FST进行优化.
FST怎么做?详见另一篇文章史上最详细FST解释
LINK:州区划分
把题目中四个条件进行规约 容易想到不合法当前仅当当前状态是一个无向图欧拉回路.
充要条件有两个 联通 每个点度数为偶数.
预处理出所有状态.
然后设\(f_i\)表示组成情况为i的值.
枚举子集转移 可以发现利用FST进行优化.
FST怎么做?详见另一篇文章史上最详细FST解释