Stalker's Blog

好不容易有一场正常时间的Cf可以打，结果还爆蛋了。。。

开场做A，做了好久才做出，还WA了两发；B的思路是对的，但是因为实现问题WA了两发，还以为想错了，浪费了很久时间；C没开long long结果FST了；D没调出来；E当时不会做，今天发现是道傻逼题。

话说曾经和神犇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$。

在许多题目中都要解决这样的问题。

这片博客主要讨论的就是解决该问题的一些算法。

话说前几天（似乎是很久很久以前）写了数论相关。

怎么说也应该写几道题，然而因为我太傻了写的都是傻逼题。

一些很基础的数论算法。

数学太弱了，写得烂，没什么办法。

本文大量参考、引用《算法导论》第31章内容。

多项式乘法是$FFT$的一个很常见的应用，所以就从它开始讲起。

这回不是傻题了。

然而我讨厌数学题。

简单数学题。

神题。

简单数学题。

NOIP结束后，感觉要爆蛋了，天天都在浪，于是决定打场VP冷静一下。

数学+二分。

公式推一推就好了。

数学题。

又是数学题。。

DP。

奇怪的数学题。。

我讨厌数学题。

数学+DP。

数学题。