9~10月份。
主要清理一下自己的任务计划。
P4071 排列计数
组合数问题。求有 \(m\) 个正好在自己的位置上的 \(n\) 阶排列数。
根据zh讲的数学思路，不好解决的问题考虑反面。于是就变成了：在 \(n\) 个数中选出 \(n – m\) 个数使它们错排，而剩下的都填自己，唯一确定，所以可以直接不考虑。
设 \(D(n)\) 表示 \(1\) ~ \(n\) 错排的方案数，那么答案就是 \(C^m_n \cdot D(n-m)\)。
\(C^m_n = \frac{n!}{(n-m)!\cdot m!}\) 可以线性递推初始化阶乘，但是有除法还需要取模，这就相当于乘上除数的乘法逆元（对于模数而言）。
逆元的定义：定义 \(a\) 在模 \(P\) 意义下的乘法逆元是 \(x\)，其中 $ ax \equiv 1(mod$ \(P)\)。
而这个题我用的最简单的求逆元方法：费马小定理，不解释，得到 \(x = a^{p – 2}\)。
接着，怎么求错排数？
这样考虑。目前有一个 \(1\) ~ \(i-1\) 的排列，接着加入一个数 \(i\)。
·\(1\) ~ \(i-1\) 为错排，那么拿 \(i\) 与任意一个 \(1\) ~ \(i-1\) 的交换，都是一种新的 \(1\) ~ \(i\) 错排。对于这种特定的 \(1\) ~ \(i-1\) 的排列，共有 \(i-1\) 种新的排列可以这样生成。
·\(1\) ~ \(i-1\) 有一个 \(k\) 在自己的位置上，其他的 \(i – 2\) 个都是错排，那么将 \(i\) 和 \(k\) 交换位置，又是一种新的 \(1\) ~ \(i\) 错排。对于这种特定的 \(1\) ~ \(i-1\) 的排列，共有 \(i-1\) 种新的排列可以这样生成。
不难证明这样可以做到不重不漏，其他新的构造都会有重或者不满足，所以可以推出 \(D(n) = (D(n-1) + D(n-2)) \cdot (i-1)\)。
最后，我们将这题先 \(O(n)\) 预处理求阶乘和错排，再对于每对 \(n\) 和 \(m\) 都求出 \(n! \cdot {((n-m)! \cdot m!)}^{P-2} \cdot D(n-m)\) 再取模即可。
P3396 哈希冲突
根号分治。
有一种 \(O(n^2)\) 预处理，\(O(1)\) 修改的做法。维护 \(ans_{p,k}\) 表示所有模 \(p\) 余 \(k\) 的 \(i\) 的 \(\Sigma v_i\)，然后在输入 \(v_i\) 时，对于每一个 \(p\)，\(ans_{p,i\%p} += v_i\)。
于是不难想到，对于 \([1,\sqrt n]\) 的 \(p\)，\(i\) 的数量会多一些，于是我们对于这个范围的 \(p\) 进行预处理式求解，其他的直接暴力求和。当然只需要在修改的时候循环模数 \(p\) 修改 \(ans\) 值。
这样就可以 \(O((m+n)\cdot \sqrt n)\) 解决，妙哉。
根号分治准备之后找题练练。
原文地址：http://www.cnblogs.com/Ziqqurat/p/16852863.html
