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