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\),那么有:
\[f_n = f_{n - 1} + (n - 1) \times f_{n - 2} \]\[v_i = \dfrac{i! - f_i}{2} \] 标签:取模,排列,校内,一个,数错,极端,当且,数量 From: https://www.cnblogs.com/OIerBoy/p/17658397.html