幂和

首先我们从求前 n 个整数的平方和开始,也就是

 S_n = \sum_{i=1}^n n^2

然后可以尝试对 S_n 进行“扰动”,就像这样

 \begin{eqnarray*}S_n + (n + 1)^2 &=& \sum_{i=0}^n (i+1)^2 \\ &=& \sum_{i=0}^n (i^2 + 2i + 1) \\ &=& S_n + 2\sum_{i=1}^n i + (n + 1) \\ \end{eqnarray*}

最后发现 S_n 竟然被消掉了,“扰动”失败了,但是我们注意到这求出了 \sum_{i=1}^n i 的公式

所以会想,可不可以用更高的 C_n = \sum_{i=1}^n i^3 来求出 S_n

 \begin{eqnarray*}C_n + (n + 1)^3 &=& \sum_{i=0}^n (i+1)^3 \\ &=& \sum_{i=0}^n (i^3 + 3i^2 + 3i + 1) \\ &=& C_n + 3S_n + \frac{3n(n + 1)}{2} + (n + 1) \\ \Rightarrow S_n &=& \frac{(n+1)^3 - \frac{3n(n + 1)}{2} - (n + 1)}{3} \\ &=& \frac{n(n+\frac{1}{2})(n+1)}{3} \end{eqnarray*}

于是这样成功地求出了 S_n 的公式,既然如此,我们又会去尝试计算更高阶的幂和

Read More

[数论]线性求所有逆元的方法

前几天在看 lucas 定理的时候发现要求 1,~2,\cdots,p-1\bmod p 的逆元,然后就看到了一个 \Theta(n) 的做法发现太神了,虽然想起来是挺简单的

这个做法实际上是这样的,首先 1^{-1} \equiv 1 \pmod p

然后我们设 p = k\cdot i + r,~r < i,~1 < i < p

再将这个式子放到\mod p 意义下就会得到

k\cdot i + r \equiv 0 \pmod p

两边同时乘上 i^{-1}\cdot r^{-1} 就会得到

 \begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}

于是就可以从前面推出当前的逆元了,代码也就一行

[数论]Miller-Rabin素性测试

如果给出一个正奇数 n,要判断它是不是素数,有一个最简单暴力的方法,就是从 2 开始一直试到 \sqrt n,这样的话能保证结果绝对正确,但是,时间复杂度也就是 \Theta (\sqrt n),当 n 的规模到达 10^{30} 甚至更高的级别的时候,就不能在可以忍受的时间内看到结果了。尤其是构造 RSA 密码体制时所需要用到的,找一个极大的素数。

那么,有没有一个比较快的方法来判断一个数是不是素数呢?

Read More

FFT用到的各种素数

是这样的,这几天在写 FFT,由于是在模意义下的,需要各种素数……

然后就打了个表方便以后查了、

如果 r \cdot 2^k + 1 是个素数,那么在\bmod r \cdot 2^k + 1意义下,可以处理 2^k 以内规模的数据,

2281701377=17\cdot 2^{27}+1 是一个挺好的数,平方刚好不会爆 long long

1004535809=479\cdot 2^{21}+1 加起来刚好不会爆 int 也不错

还有就是 998244353=119 \cdot 2^{23}+1

下面是刚刚打出来的表格(g\bmod (r \cdot 2^k + 1)的原根)

Read More

BZOJ-3157. 国王奇遇记

题目大意是要求下面这个式子

 \begin{eqnarray*} \sum_{i=1}^n m^i \cdot i^m \end{eqnarray*}

这个题目有三个版本:

BZOJ-3157 m \leq 200

BZOJ-3516 m \leq 1000

BZOJ-4126 m \leq 500000

这篇文章介绍 \mathcal O(m^2)\mathcal O(m) 两种做法

为了方便,定义一个函数 f(i)

 \begin{eqnarray*} f(i) = \sum_{k=1}^n k^i \cdot m^k \end{eqnarray*}

然后使用“扰动法“

 \begin{eqnarray*} (m - 1) \cdot f(i) & = & \sum_{k=1}^n k^i \cdot m^{k + 1} - \sum_{k=1}^n k^i \cdot m^k \\ & = & \sum_{k=1}^{n + 1} (k - 1)^i \cdot m^k - \sum_{k=1}^n k^i \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{k=1}^n m^k \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot k^j \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \sum_{k = 1}^n k^j \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot f(j) \\ \end{eqnarray*}

然后这个算法的复杂度是 \mathcal O(m^2) 的,但是这题最快可以做到 \mathcal O(m) 的!

Read More