0811T1 计数练习

题意

作为一名普及组选手，小 \(A\) 喜欢数数。

一天，小 \(A\) 学习了排列相关的知识。定义一个长度为 \(n\) 的序列 \(p_{1...n}\) 是一个 \(n\) 阶排列，当且仅当 \(p_{1...n}\) 都是 \([1, n]\) 中的正整数且它们两两不同。

小 \(A\) 想数排列。为了让数排列更有趣，小 \(A\) 决定加入一个限制：

对于一个 \(n\) 阶排列 \(p\) ，小 \(A\) 会构造一个长度为 \(n\) 的序列 \(Q(p)\) ，其中 \(Q(p)_{p_i} = i\) 。小 \(A\) 称排列 \(p\) 是优秀的，当且仅当 \(p\) 的字典序严格小于 \(Q(p)\) 。即存在一个 \(i\) 使得 \(\forall 1 \le j < i, p_j = Q(p)_j\) 且 \(p_i < Q(p)_i\) 。

现在，小 \(A\) 想了一个数 \(n\)，他希望对于每个 \([1, n]\) 间的 \(m\)，计算好的 \(m\) 阶排列数量， 在开始数这样的排列数量前，小 \(A\) 给了你一个质数 \(mod\) ，希望你先求出好的 \(m\) 阶排列 数量对 \(mod\) 取模的结果。

为了避免极其大的输出，设 表示好的 阶排列数量对 取模的结果，你只需要 输出 ，即所有 的异或和。这样小 在自己数错的时候就有大约 的概率发现自己数错了，并重新数一遍。

Sol

由于 \(Q(Q(p)) = p\)，也就是说一个排列的逆排列就是自己。

如果从 \(p\) 和 \(Q(p)\) 的视角出发，那么字典序的关系就是相反的。

那么一个排列一定会贡献 \(1\) 除非 \(p = Q(p)\)。

容易发现，如果所有轮换大小不超过 \(2\)，那么组成的排列的逆排列就是自己。

我们记这样的 \(n\) 阶排列数量为 \(f_n\)，那么有：