本文主要是介绍【校内模拟】【18-10-16】膜法 【组合数学】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
(拖更N天终于想起来我还有博客 )
(校内模拟的题面&代码联赛后解除封印~)
题解
1.0 认(hu)真(luan)分析
一开始看这道题看了半天,还以为是什么区间查询之类的题,后来认认真真读了读样例,才理解过来——这是个组合数学题!
当且仅当存在至少一个环节,选择的书不同,或者在同一本魔法书上选取的咒语不一样。
这不就是组合数嘛……
分摊到每一步上,在 li 处有 li-k+1 种选择,在 li+1 处有 li+1-k+1 种选择……然后最后在 ri 处有 ri-k+1 种选择。
又因为l到r是连续的一段区间,所以每一步的方案数可以表示如下:
(借用于ZXY大佬的blog,%%%其实是我打不来)
按照这个式子预处理一波阶乘和逆元,可以得到60分。
1.1正解
我们发现,刚才之所以拿不了满分,主要是在计算上花了很多时间。
那么我们可以把式子简化一些吗?
下面又是蒟蒻的我想不到的了
(再次借用于%%%神仙zxy的博客 )
我们要运用一些组合数学的定理:
然后……
然后变成这样就非常方便了对吧?
这样一来,对于每一次个l和r,我们只需要计算两个值就可以求出这一段的方案总数,也就是O(1)的处理时间。预处理本身也只需要O(N)不到的复杂度。
于是,我们就开心的A掉这道题了~
总结:
组合数学一直是数论专题的重要考点之一,对于这方面的各种推论和运用,我们需要记住几个常用的定理和公式,一般就能保证自己做题时思路的正确性了。
还有重要的一点(就是我今天挂掉的主要问题 ),取模运算时一定要把除法转化为乘上逆元!要不然就算你的算法正确也照样GG了~
这篇关于【校内模拟】【18-10-16】膜法 【组合数学】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!