话说曾经和神犇JYT讨论过不同底数的对数在渐进记号中是否相等,即对于常数$a,b$,$\Theta\left(log_a n\right)$是否等于$\Theta\left(log_b n\right)$。我当时认为是不相等的,显然我是傻掉了。。。
根据对数的换底公式,$\log_a n=\large{\frac{\log_b n}{\log_b a}}$,因为$a,b$是常数,所以它们只相差常数倍。。。
话说曾经和神犇JYT讨论过不同底数的对数在渐进记号中是否相等,即对于常数$a,b$,$\Theta\left(log_a n\right)$是否等于$\Theta\left(log_b n\right)$。我当时认为是不相等的,显然我是傻掉了。。。
根据对数的换底公式,$\log_a n=\large{\frac{\log_b n}{\log_b a}}$,因为$a,b$是常数,所以它们只相差常数倍。。。
考虑这样一个问题:给出非负整数$n,m$和正整数$p$,分别求${n\choose m}\bmod p$。
在许多题目中都要解决这样的问题。
这片博客主要讨论的就是解决该问题的一些算法。
KMP算法可以在$\mathcal{O}\left(n+m\right)$的时间内高效地完成单个模板串的字符串匹配问题。但是对于多模板串的情况,算法的时间复杂度只有$\mathcal{O}\left(\sum\left(n+m_i\right)\right)$,就不能满足需求了。
这时可以考虑使用AC自动机。
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com