arrow_back数论共126篇文章

https://www.luogu.com.cn/blog/s-r-f/oi-bi-ji-shuo-wei-dp-ge-ji-dui-shuo-wei-dp-di-yi-dian-li-xie

定义

H_n = \begin{cases} \sum_{i=1}^n H_{i-1} H_{n-i} & n \ge 2 \\ 1 & n = 0, 1 \end{cases}

https://www.luogu.com.cn/blog/wucstdio/duo-xiang-shi-suan-fa-di-chang-shuo-wen-ti

https://www.luogu.com.cn/blog/user7035/duo-xiang-shi-zong-jie

http

问题

求\displaystyle \sum\limits_{i=1}^n i^k

1258 序列求和 V4

普通求法:

$$ (n+1)^{k+1}-

给定序列A,B,设

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

分别当\oplus是or,and,xor时求出C

思想

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

$A\rightarrow \te

Miller Rabin

判断一个数是否为素数O(\log n)

前置知识:

1. 费马小定理

   若p为素数,a^{p-1}\equiv 1 \pmod p

2. 二次探测定理

   若p为质数x^2\equiv 1 \pmod p,那么$x\equi

第一类斯特林数

定义

• s(n,m)表示将n个元素分成m个圆排列的方案数

• 记作\begin{bmatrix}n\\m\end{bmatrix}

递推式

$$ \begin{bmatrix}n\m\end{bmatrix}=\begin{bmat

普通的单模式串匹配

给定模式串A(|A|=m)、文本串B(|B|=n)，需要求出所有位置p,满足B串从第p个字符开始的连续m个字符，与A串完全相同

定义匹配函数C(x,y)=[A(x)-B(y)]^2,若A的第x个字符与B的第y个字符匹配

前置知识

1. 极限
2. 导数与高阶导数

下面简单介绍下极限与导数的概念

极限

\displaystyle \lim_{x\to \infty} \frac 1x=0表示当x无限趋近于无穷大时\frac 1x无限接近于0

$\displaystyle \li

数学常数

e,作为数学常数,是自然对数函数的底数.

e是一个无理数,并且是超越数

e=2.71828182845904523536\cdots

e又称自然常数、欧拉数.

先引入关于e的有趣问题

银行问题

一笔钱存在在银行,假设这笔钱为1,

假设一