zcmimi's blog

categories/算法/数论/共18篇文章

avatar
zcmimi
2020-08-27 22:46:00
avatar
zcmimi
2020-08-24 19:20:00

给定序列A,B,设

C_i=\sum_{j\oplus k=i}A_j \times B_k

分别当\oplusor,and,xor时求出C

思想

\text{fwt}_A为对A进行快速沃尔什变换后的序列

$A\rightarrow \te

avatar
zcmimi
2020-07-09 22:36:00

平面上n+1个点可以确定一个n次多项式F(x)

拉格朗日插值法可以根据n+1个点确定一个n次多项式

设这n个点为(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)

构造多项式 $\displaystyle \elli(x)=\prod{j=

avatar
zcmimi
2020-07-05 15:56:00

阶:

定义:

m>1\gcd(a,m)=1,那么使得a^r \equiv 1 \pmod m成立的最小的正整数r称为a对模m的阶,记为\delta_m(a),或ord_m a

定理:

  1. m>1gcd(a,m)=1,满足$a^n\
avatar
zcmimi
2020-06-25

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

avatar
zcmimi
2020-03-15 17:10:00

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另

avatar
zcmimi
2020-03-14 22:46:00

数论函数

  1. 加法

    逐项相加

    (f+g)(x)=f(x)+g(x)

  2. 数乘

    (xf)(n)=x\cdot f(n)

定义

两个数论函数的狄利克雷卷积∗

t=f*g等价于

$$t(n)=\sum_{i|n}f(i)

avatar
zcmimi
2020-03-12 20:40:00

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

$$ \mu (i)= \begin{cases} 1,i=1 \ (-1)^k,i=p_1\times p_2\times \dots \times p_k \ 0,rest \end{cases

avatar
zcmimi
2020-03-07 15:50:00

扩展中国剩余定理

给定方程组:

$$ \begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \ x\equiv a_2\ ({\rm mod}\ m_2) \ ... \ x \equiv a_n\ ({\rm mod}\ m_n) \end{cas

avatar
zcmimi
2020-03-02

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p} \cdot C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大

1/2
Search
search