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

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性