zcmimi's blog

arrow_back数论共123篇文章

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非常大

avatar
zcmimi
2020-02-27

NTT基本上跟FFT一样,就是把单位根换成了原根(原根和单位根一样具有FFT需要的特殊性质)

前置知识:

  1. FFT

  2. 原根

原根的性质

p是质数,g为模p的原根,n|(p-1),$g_n=g^{(

avatar
zcmimi
2020-02-25

FFT

fst fst tle

DFT: 离散傅里叶变换

IDFT: 离散傅里叶逆变换

FFT: 快速傅里叶变换

FNTT/NTT: 快速傅里叶变换的优化版

FWT: 快速沃尔什变换,利用类似FFT的东西解决一类卷积问题

MTT: 毛爷爷的FFT,非常nb/任意模数

FMT: 快速莫比乌斯变化

(摘自https://www.cnblogs.com/zwfymqz/p/8244902.html)

为什么要用到FFT呢?

以高精度乘法举个例子:

你现在要计算a\times b,a,b>10^{1000000}

len_a=n,len_b=m

如果用普通的高精度乘法\mathcal{O(nm)},直接tle

但是FFT可以做到\mathcal{O((n+m) \log (n+m))}

原理: 先把多项式转化为用点值表示\mathcal{O(n \log n)}

然后再用点值相乘来计算\mathcal{O(n)}

然后再通过点值还原多项式

avatar
zcmimi
2020-02-19

求解关于x的方程:

y^x \equiv z \pmod p

bsgs

\gcd(y,p)=1

解法:

x=am-b

那么y^{am} \equiv z\cdot a^b \pmod p

右边:

枚举b的取值[0,m-1],计算右边的

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-x

avatar
zcmimi
2020-01-10

四边形不等式

定义

对于任意a_1\le a_2<b_1\le b_2,满足m[a_1,b_1]+m[a_2,b_2]\le m[a_1,b_2]+m[a_2,b_1]

那么m[i,j]满足四边形不等式

要证明m[i,j]满足四边形不等式可以用打表或数

avatar
zcmimi
2019-12-01

容斥

容斥原理

  • 求具有n个属性之一(并集)的元素的个数

  • 求不具有n个属性中任何一个(交集)的元素的个数

两个集合的并集

|A \bigcup B| = |A|+|B|-|A \bigcap B|

三个集合的并集

$ \begin{aligned

avatar
zcmimi
2019-10-20

Lucas定理

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

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

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

avatar
zcmimi
2019-01-21 11:31:55

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

设$r=a \b

avatar
zc
2020-10-19 16:24:55

查看原题

点击跳转

n个位置中选出m个位置后剩余n-m个位置错排

{n\choose m}\cdot D_{n-m}

3/13
Search
search