AT_abc214_g

· · 题解

如果是单独的一个序列，直接错排即可，这道题尝试建图，把 p_i 和 q_i 连起来。
发现每个点至多两个度，所以最后得到的图由很多环或者单链拼接而成，每一条边都对于序列中一个数，不合法的情况便是这个数选择了这条边两端连接的两个点之一。

回到错排的做法，需要钦定某些位置不合法，尝试在这道题使用该方法，定义 f_i 表示至少有 i 个数错位的方案数，定义 g_i 表示恰好有 i 个数错位的方案数，得到

\begin{aligned} f(i) &= \sum_{j = i}^{n} \binom{j}{i} g(j) \\ \Leftrightarrow g(i) &= \sum_{j = i}^{n} (-1)^{j - i} \binom{i}{j} f(i) \end{aligned}

发现每个环都互不影响，贡献只于环的大小相关，于是拉出来考虑每个环如何算。
对于一个大小为 c 的环，要使它错位 k 个位置，方案数为 \binom{2c - k}{k} + \binom{2c - k - 1}{k - 1}。
然后暴力卷积拼答案即可。