题意相当于计数满足如下条件的长度为 的排列 ： 把条件转换一下，就是对于每个 ，要么 （自己匹配自己），要么存在 满足 （即找一个别的位置匹配）；考虑 比较小的时候暴力怎么做，因为 特别小，所以考虑状压 DP：由于 ，所以运用 NOI2023 桂花树 的方法，假设当前考虑到了第 位，用一个集合 表示第 位的状态（ 表示该位已经匹配， 表示待匹配）， 表示这种状态下的答案，最终答案即为 。 有如下几种转移（下文中 表示二进制下的按位左移，其他符号类似）： ： 自己匹配自己； ：将 设为未匹配； ：需要满足 的第 位为 ，用 匹配前面的一个未匹配的 ； 特判一下...