想探索一下在 OS 课上写一个指导来让同学们可以像系统一样选择 spike 来进行 RISC-V kernel 调试。当时系统三助教的时候用过，但是 spike 是学长改过的 riscv-isa-cosim（加了 CJ 也就是 difftest 的部分），这个目前已经有段时间没更新了，所以在尝试使用最新版本 OpenSBI（启用 PIE 编译）的时候无法加载 ELF（还不支持 PIE），于是就更换成了最新的 spike，然后就有了以下的调试过程。

今天一天都在修 ManimGL 里的 SVGMobject，还是比较有收获的，写篇文章记录一下
起因是 fran 给了一个在 ManimGL 里表现怪异的 svg 文件：formula.svg

< #2

解码（11、Annex B）

简要的解码过程：

1. 定位并获取图像中的二维码，并把图像中的黑白块提取为 1 和 0
2. 读取格式信息

纠错码编码（7.5）

纠错容量（7.5.1）

纠错字（error correction codewords）可以纠正两种错误，一种是比如无法扫描或无法解码的已知位置的错误字（erasures），一种是未知位置的错误字（errors），一个 erasures 可以由一个纠错字纠错，而一个 errors 需要两个纠错字来纠错

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

基础描述（5.3、6.1）

• 块位置：左上角为原点 (0, 0) 向下x+，向右y+
• 版本表示：Version V-E（其中V是版本号，E是纠错等级）
• 数据表示：黑块-1 白块-0（可以带背景全部反色）
• 大小：从版本1到版本40依次是 21x21 ～ 177x177（每增加一个版本，边长增加4）

最近几次比赛遇到过好几次二维码的题目，打算好好来读一读标准文档 ISO/IEC 18004:2015
文档 6.1 前面的内容不多，就从它后面开始记了

Table of Content

• 「QRCode 标准阅读」#1 构成及数据编码
  对应文档中的 6.1~7.4 部分
• 「QRCode 标准阅读」#2 纠错码编码与图像生成
  对应文档中的 7.5～7.10 部分
• 「QRCode 标准阅读」#3 解码纠错过程
  对应文档中的 11 部分以及补充了 PGZ 解码相关内容

前言

前段时间，GZTime也跟我聊过一些关于lambda演算的东西
学Haskell的时候也总是能听说这个东西
看起来挺有意思，来学学_(:з」∠)_

学习一门新语言之Haskell

前言

Haskell学的差不多了，也没啥事想干了
GZTime之前也跟我推荐过Rust挺好玩的
这几天看一看
一样，没有教程，只是我的笔记而已

Foldable

Foldable是表示可以折叠（fold）的类型类，在Data.Foldable中定义，这使得和fold相关的函数可以用在任意Foldable的实例类型上。它的定义是：

Haskell中的函子单子等都与范畴论（category theory）有很多联系，所以打算简单了解一下范畴论的相关内容。

范畴论是数学的一门学科，以抽象的方法处理数学概念，将这些概念形式化成一组组的“物件”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明。

———— 维基百科

范畴（Category）

范畴本质上是一个简单的集合，一个范畴$\mathbf{C}$包含三个组成成分：

Semigroup

半群（semigroup）是一个集合$S$，它需要指定一个二元运算符$\oplus$，并且满足

$$
a\oplus b \in S\quad a, b\in S
$$

以及结合（associative）律：

$$
(a\oplus b)\oplus c = a\oplus (b\oplus c)
$$

这个二元运算符在Haskell的Semigroup中被定义为<>函数：

Functors

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

Input/Output

运行Haskell程序

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

Types

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

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

Higher Order Functions

Currying

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

基础运算

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

学习一门新语言之Haskell

前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

模板地址: 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)$

1
2
3
4

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筛法

1
2
3
4
5
6
7
8
9
10
11

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;
    }
}

欧拉线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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$

1
2
3
4
5
6
7
8
9

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$

1
2
3
4
5
6
7

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;
}

使用位运算:

1
2
3
4
5

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$互质的整数个数

求值

1
2
3
4
5
6
7
8
9

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;
}

筛欧拉函数表

1
2
3
4
5
6
7
8
9

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$不为质数

递归求解

1
2
3
4
5

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

筛逆元表

1
2
3
4
5
6
7

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$两两互质

1
2
3
4
5
6
7
8
9
10

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$不一定两两互质

1
2
3
4
5
6
7
8
9
10
11
12
13

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$为质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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}$$
线性筛:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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];
		}
	}
}

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