zcmimi's blog

categories/note/共63篇文章

avatar
zcmimi
2020-08-27 22:46:00
avatar
zcmimi
2020-08-27 16:32:00

问题

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

1258 序列求和 V4

普通求法:

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

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-08-05 10:38:00

Miller Rabin

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

前置知识:

  1. 费马小定理

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

  2. 二次探测定理

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

avatar
zcmimi
2020-07-25 13:25:00

第一类斯特林数

定义

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

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

递推式

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

avatar
zcmimi
2020-07-22 19:57:00

普通的单模式串匹配

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

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

avatar
zcmimi
2020-07-16 19:40:00

前置知识

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

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

极限

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

$\displaystyle \li

avatar
zcmimi
2020-07-12 17:14:00

数学常数

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

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

e=2.71828182845904523536\cdots

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

先引入关于e的有趣问题

银行问题

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

假设一

avatar
zcmimi
2020-07-11 07:23:00

有一类普通莫队不可解的问题就是在转移区间过程中,可能出现删点或加点操作其中之一无法实现的问题,这时可以使用回滚莫队算法

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=

2/7
Search
search