AGC008E Next or Nextnext

题意：给定一个长度为 的 序列 ，问有多少长度为 的排列 ，满足对于任意 有 或 。

答案对 取模。

，时限 。

---

根据排列 ，对每个 连边 ，会形成若干个有向环。

约束相当于：在 点两步数以内要能走到 。

根据序列 ，对每个 连边 ，会形成基环内向树森林。

先观察一个 图可能对应怎样的 图：

• 情况 ：全部有

  会形成一个和原来相同的环。

• 情况 ：全部有

  若环长为奇数，会形成一整个环，但和原来不同。

  若环长为偶数，会形成两个等大的小环。

  

• 情况 ：部分有 ，部分有

  

  不难发现，会得到一个特殊的基环树，环上挂着几条链。

接下来考虑反映射，即由 图得到 图。

• 环

  记 中大小为 的环的个数为 ，考虑这些环组合的方案。

  枚举配对的环的个数 。

  • 从 个环中选出 个：。

  • 将 个环配对：。

  • 每对环有 种拼法（旋转） ：

  • 当 为奇数且 时，落单的环可以生成两个不同的环 ：

• 基环树

  要把链塞入环的缝隙中。

  

  是一段外链的长度（不包括在环上的链头）， 是该链头到下一个链头之间的边数。

  手玩可以发现，若 则方案数为 ，若 方案为 ，若 方案为 。

  

  利用乘法原理计算答案即可。

复杂度 。