函子（Functor）是一个类型类（typeclass），和其他类型类一样，它规定了其实例类必须实现的功能（例如Eq类型类规定了它的实例必须是可以比较是否相等的），Functor规定类它的实例必须是可以进行映射的。Functor要求使用fmap :: (a -> b) -> f a -> f b 函数来实现这个功能，它接收一个a -> b类型的函数、一个内部元素为a类型的函子，返回一个内部元素为b类型的函子

阅读全文

2021-07-07发表2021-07-25更新26 分钟读完 (大约3830个字)

「Learn Haskell」#4 输入输出与文件

< #3

#5 >

Input/Output

运行Haskell程序

不在GHCi中运行一个Haskell程序有两种方式：

阅读全文

2021-07-07发表2021-10-21更新22 分钟读完 (大约3235个字)

「Learn Haskell」#3 类型与类型类

< #2

#4 >

Types

Haskell有一个静态类型系统，任何变量、函数都会具有类型，并且有类型判断功能，没给出的类型会自动识别。
Type的首字母全为大写，常用的有：

Int：整型，有上下界范围，-2147483647～2147483648

阅读全文

2021-07-07发表2021-07-25更新21 分钟读完 (大约3120个字)

「Learn Haskell」#2 高阶函数与模块

< #1

#3 >

Higher Order Functions

Currying

Haskell中的函数是柯里化（Currying）的，可以看作所有函数都只接收一个参数，而接收两个参数的函数实际上是这个函数接收了第一个参数后返回了一个接收第二个参数的函数，然后用这个函数接收第二个参数，返回最终的结果。比如max函数，它的类型签名是：

阅读全文

2021-07-07发表2021-10-21更新12 分钟读完 (大约1787个字)

「Learn Haskell」#1 基础语法与函数

< #0

#2 >

基础运算

+ - * / ()：加减乘除
div：整除
mod：取模
True False：布尔值

阅读全文

2021-06-21发表2022-02-16更新3 小时读完 (大约25386个字)

「Learn Haskell」#0 总章

学习一门新语言之Haskell

前言

之前一直很好奇函数式编程，觉得Haskell挺有意思的，想学学
现在高考完放假了，可以有时间具体学一学了
这里没有Haskell的教程，只有我在学习Haskell时写下的笔记

阅读全文

2020-05-06发表2021-06-21更新manim / 笔记10 分钟读完 (大约1552个字)

修复manim中Text类的bug

在使用manim时,对于Text类,会有一些bug,我尝试修复了它们

在shaders分支下无法使用Text类
Text文字的stroke边框不完整,导致显示stroke会非常难看
含有空格的Text的空格不在文字内部,而在ORIGIN的位置,导致Transform时会有字符在原位置和ORIGIN之间 ~~反复横跳~~
Text文字的默认大小要比TextMobject大,不容易像TextMobject一样控制大小

这些问题已经通过#1030修复到了manim的master分支中

阅读全文

2020-04-30发表2020-05-05更新C++算法 / 笔记8 分钟读完 (大约1158个字)

树上莫队-笔记 /「SPOJ 10707」COT2-题解

通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询树上的多区间问题时,可以使用 树上莫队 来解决

主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作

阅读全文

2020-04-30发表2020-05-05更新C++算法 / 笔记8 分钟读完 (大约1186个字)

回滚莫队-笔记 /「AtCoder 1219」歴史の研究-题解

通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add操作,而不容易实现del的情况

通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似达到del的效果

阅读全文

2020-04-29发表2020-05-05更新C++算法 / 笔记7 分钟读完 (大约1089个字)

带修莫队-笔记 /「Luogu P1903」数颜色-题解

通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改

比如这道题目,需要实现以下目标

查询$[L,R]$区间内不同颜色画笔的种数
将$pos$处的画笔替换为$color$颜色

达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队

阅读全文

2020-04-29发表2020-05-05更新C++算法 / 笔记7 分钟读完 (大约1013个字)

浅析莫队算法的时间复杂度

这篇文章来记录一下莫队算法时间复杂度的简单(~~不严谨~~)计算

首先分析一下莫队算法的时间复杂度有哪些方面构成

对询问Query数组的排序
区间左指针的移动
区间右指针的移动

阅读全文

2020-04-18发表2020-05-05更新manim / 笔记3 分钟读完 (大约511个字)

manim教程系列-颜色笔记

这篇文章是在写 manim教程系列视频 的颜色部分时做的一些笔记,包括整个视频的结构和写代码时了解的一些用法的笔记
视频已经发布,地址:BV1vZ4y1x7hT

阅读全文

2019-09-22发表2020-05-05更新C++算法 / 笔记 / 图论6 分钟读完 (大约927个字)

「图论算法」树上并查集 dsu on tree

$dsu\ on\ tree$($disjoint\ set\ union\ \text{on tree}$)算法，也称 __树上并查集__。使用了并查集的按秩合并(启发式合并)的方法，结合 树链剖分 中的 轻重儿子划分 ，对 树上暴力统计 进行了优化。使用这个算法需要满足以下两个条件：

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构6 分钟读完 (大约862个字)

「数据结构」线段树

线段树($Segment\ Tree$)是一种基于分治思想的__二叉树__形数据结构，可以用于__区间__上的数据维护，它可以维护以下值

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构4 分钟读完 (大约538个字)

「数据结构」左偏树(可并堆)

左偏树($Leftist\ Tree$)，是一种 __可以合并的堆状结构__，支持以下操作

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构3 分钟读完 (大约512个字)

「数据结构」树状数组

树状数组($Binary\ Indexed\ Trees$)是一个维护__前缀和__的数据结构，需要支持以下操作

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构5 分钟读完 (大约719个字)

「数据结构」并查集

并查集($union-find\ \ set$)是一种可以__动态维护__若干个不重叠的__集合__，并支持__合并与查询__的数据结构，支持以下两种基本操作：

阅读全文

2019-05-08发表2021-07-07更新C++算法 / 笔记9 分钟读完 (大约1321个字)

算法笔记-数论

模板地址: GitHub

欧几里得算法(Euclid algorithm)

1
2
3

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

lcm(a, b) = a / gcd(a, b) * b

扩展欧几里得算法(exGCD)

目标: 寻找一对整数$(x, y)$,使$ax+by=gcd(a,b)$

void exgcd(LL a, LL b, LL& d, LL& x, LL& y) {
    if (!b) { d = a; x = 1; y = 0; }  //d为gcd(a, b)
    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}

裴蜀定理

$ax+by=c$且$x,y$全为正整数,则当且仅当$gcd(a, b)|c$

素数相关

Eratosthenes筛法

bool vis[maxn];
int prime[maxn];
void getprime(int n) {
    int m = (int)sqrt(n + 0.5), num = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= m; ++i) if (!vis[i]) {
        prime[++num] = i;
        for (int j = i * i; j <= n; j += i) vis[j] = 1;
    }
}

欧拉线性筛

void getprime(int n) {
    vis[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            int v = i * prime[j];
            if (v > n) break;
            vis[v] = true;
        }
    }
}

素数定理

$$
\pi(x) \sim \frac{x}{\ln x}
$$

$Miller-Rabin$素数测试

原理:费马小定理
若$a^{n-1}\equiv 1\pmod n$,$a$取值越多,可以近似认为$n$为质数
使用二次探测定理改进卡卡迈尔数(合数$n$对于任何正整数$b$,都满足$gcd(b, n)=1\ \ b^{n-1}\equiv 1\pmod n$)的bug

LL Random(LL n) { return (LL)((double)rand() / RAND_MAX * n + 0.5); }
bool Witness(LL a, LL n) {
    LL m = n - 1; int j = 0;
    while (!(m & 1)) { j++; m >>= 1; }
    LL x = pow_mod(a, m, n);
    if (x == 1 || x == n - 1) return false;
    while (j--) { x = x * x % n; if (x == n - 1) return false; }
    return true;
}
bool Miller_Rabin(LL n) {
    if (n < 2) return false; if (n == 2) return true;
    if (!(n & 1)) return false;
    for (int i = 1; i <= 30; ++i) {
        LL a = Random(n - 2) + 1;
        if (Witness(a, n)) return false;
    }
    return true;
}

模算术

$$
(a + b)\bmod n = ((a\bmod n) + (b\bmod n))\bmod n\\
(a - b)\bmod n = ((a\bmod n) - (b\bmod n) + n)\bmod n\\
ab\mod n = (a\bmod n)(b\bmod n)\bmod n
$$

快速乘 $ab\bmod n$

LL mul_mod(LL a, LL b, LL n){
    LL res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % n;
        a = (a + a) % n;
        b >>= 1;
    }
    return res;
}

快速幂 $a^p\bmod n$

LL pow_mod(LL a, LL p, LL n) {
    if (p == 0 && n == 1) return 0;
    if (p == 0) return 1;
    LL ans = pow_mod(a, p / 2, n); ans = ans * ans % n;
    if (p % 2 == 1) ans = ans * a % n;
    return ans;
}

使用位运算:

LL pow_mod(LL a, LL p, LL n) {
    a %= n; LL ans = 1;
    for (; p; p >>= 1, a *= a, a %= n) if(p & 1) ans = ans * a % n;
    return ans;
}

欧拉$\varphi$函数

$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
$\varphi(n)$表示不超过$n$且与$n$互质的整数个数

求值

int euler_phi(int n) {
    int m = (int)sqrt(n + 0.5); int ans = n;
    for (int i = 2; i <= m; ++i) if (n % i == 0) {
        ans = ans / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

筛欧拉函数表

int phi[maxn];
void phi_table(int n) {
    for (int i = 2; i <= n; ++i) phi[i] = 0; phi[1] = 1;
    for (int i = 2; i <= n; ++i) if (!phi[i])
        for (int j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
}

同余式定理

欧拉定理

若$gcd(a, n) = 1$,则$a^{\varphi(n)}\equiv 1\pmod n$

费马小定理

若$p$为质数,则$a^{p-1}\equiv 1\pmod p$

威尔逊定理

若$p$为质数,则$(p-1)!\equiv -1\pmod p$

乘法逆元

$$a\div b\bmod n = a\times b^{-1}\bmod n$$
$b^{-1}$称为$b$在模$n$意义下的逆元

$n$为质数

使用费马小定理, $a^{-1} = a^{n - 2}$

$n$不为质数

递归求解

LL inv(LL a, LL n) {
    LL d, x, y;
    exgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

筛逆元表

int inv_table[maxn];
void getinv(int n, int p) {
    inv_table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv_table[i] = (LL)(p - p / i) * inv_table[p % i] % p;
    }
}

同余方程

$ax\equiv b\pmod n$可以化为$ax+ny=b$使用扩展欧拉定理解决

中国剩余定理(China Remainder Theorem)

求解$x\equiv a_i\pmod {m_i}$满足$m_i$两两互质

LL crt(int n, int* a, int* m) {
    LL M = 1, d, y, x = 0;
    for (int i = 0; i < n; ++i) M *= m[i];
    for (int i = 0; i < n; ++i) {
        LL w = M / m[i];
        exgcd(m[i], w, d, d, y);
        x = (x + y * w * a[i]) % M;
    }
    return (x + M) % M;
}

扩展中国剩余定理(exCRT)

$m_i$不一定两两互质

LL excrt(LL n, LL* a, LL* m) {
    LL x, y, k, M = m[0], ans = a[0];
    for (int i = 1; i < n; ++i) {
        LL A = M, B = m[i], C = (a[i] - ans % B + B) % B, gcd;
        exgcd(A, B, gcd, x, y);
        LL bg = B / gcd;
        if (C % gcd != 0) return -1;
        x = mul_mod(x, C / gcd, bg);
        ans += x * M; M *= bg;
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

离散对数(BSGS)

求解$a^x\equiv b\pmod n$满足$n$为质数

int log_mod(int a, int b, int n) {
    int m, v, e = 1, i;
    m = (int)sqrt(n + 0.5);
    v = inv(pow_mod(a, m, n), n);
    map<int, int> x;
    x[1] = 0;
    for (i = 1; i < m; ++i) {
        e = mul_mod(e, a, n);
        if (!x.count(e)) x[e] = i;
    }
    for (i = 0; i < m; ++i) {
        if (x.count(b)) return i * m + x[b];
        b = mul_mod(b, v, n);
    }
    return -1;
}

莫比乌斯反演

整除分块

整除分块可以对后面的莫比乌斯反演提供很大的优化
通过枚举可以发现$\lfloor \frac{n}{i} \rfloor$的结果会出现分块现象
例如$n=10$时
$\ \ \ i\ \ \ \ 1\ \ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ …$
$\lfloor \frac{n}{i} \rfloor\ 10\ 5\ 3\ 2\ 2\ 1\ 1\ 1\ 1\ 1\ \ \ 0\ \ \ 0\ \ \ 0\ \ \ …$
~~不难发现~~,每个块的右端点为$r=\lfloor \frac{n}{t}\rfloor (t=\lfloor \frac{n}{i}\rfloor)$

莫比乌斯函数

$$
\mu(n) =
\begin{cases}
1, & n=1 \\
(-1)^r, & n=p_1p_2p_3…p_r(\text{$p_i$为互不相同的质数}) \\
0, & else
\end{cases}
$$
性质:
$$\sum_{d|n}{\mu(d)}=[n=1]$$
$$\sum_{d|n}{\frac{\mu(d)}{d}}=\frac{\varphi(n)}{n}$$
线性筛:

int mu[maxn], vis[maxn];
int primes[maxn], cnt;
void get_mu(int n) {
	memset(vis, 0, sizeof(vis));
	memset(mu, 0, sizeof(mu));
	cnt = 0; mu[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) { primes[cnt++] = i; mu[i] = -1; }
		for (int j = 0; j < cnt && primes[j] * i <= n; ++j) {
			vis[primes[j] * i] = 1;
			if (i % primes[j] == 0)break;
			mu[i * primes[j]] = -mu[i];
		}
	}
}

2019-04-30发表2020-05-05更新C++算法 / 笔记15 分钟读完 (大约2219个字)

算法笔记-计算几何

啥也不说了,直接上代码,每个函数功能已经以注释方式给出

阅读全文

解码（11、Annex B）

纠错码编码（7.5）

纠错容量（7.5.1）

基础描述及结构（6.1、6.3）

基础描述（5.3、6.1）

Table of Content

前言

前言

Foldable

范畴（Category）

Semigroup

Functors

Input/Output

运行Haskell程序

Types

Higher Order Functions

Currying

基础运算

前言

欧几里得算法(Euclid algorithm)

扩展欧几里得算法(exGCD)

裴蜀定理

素数相关

Eratosthenes筛法

欧拉线性筛

素数定理

$Miller-Rabin$素数测试

模算术

快速乘 $ab\bmod n$

快速幂 $a^p\bmod n$

欧拉$\varphi$函数

求值

筛欧拉函数表

同余式定理

欧拉定理

费马小定理

威尔逊定理

乘法逆元

$n$为质数

$n$不为质数

筛逆元表

同余方程

中国剩余定理(China Remainder Theorem)

扩展中国剩余定理(exCRT)

离散对数(BSGS)

莫比乌斯反演

整除分块

莫比乌斯函数

最新文章

归档

标签

分类