使用模逆元计算组合问题

模逆元（modular multiplicative inverse）俗称模倒数，是指与原数的乘积和 1 同余的整数。即对于整数 $a$ 和 $n$：

$$ ax \equiv 1 \mod(n) $$

上式中 x 就是 a 对于 n 的模逆元，$a$ 与 $n$ 互质时模倒数存在，否则不存在。 它的数学意义是模倒数存在时，除以一个数和乘以它的模倒数同余，可以把除法转换为乘法。 这对于计算大数（10 以上）组合问题非常有效，适用于 Sherlock and Permutations 和 Matrix Tracing 等问题。 这类问题的都可以转化为组合问题 ${n \choose m}$，由于它的值通常会很大，我们只关心它对某个大质数 M（比如 $1e9 + 7$）的模：

$$ {n \choose m} = C_n^m = \frac{n!}{m!(n-m)!} \mod{M} $$

ArchLinux 休眠到交换文件

Linux 使用交换分区来休眠，首先冻结所有进程并申请足够的交换内存（位于磁盘），把当前内存都存进去。 然后下次启动时，initramfs 会直接加载上次休眠时的内存状态，跳过内核的 init 过程。 因此首先需要有足够大的交换分区或交换文件；再把内核指向到休眠的分区上；最后再配置 initramfs 让它加载休眠的内存文件。 官方文档请参考 Power_management/Suspend_and_hibernate#Hibernation， 本文细述如何休眠到交换文件，并对其中一些概念和细节进行了解释。

在本文讨论的范围内， 挂起（suspend）是指冻结当前的进程，保留它们的内存，并把几乎除了内存之外的设备都断电。 休眠（hibernate）是指把挂起后的内存写入磁盘并完全关机。 锁定（lock）则只是显示一个模态的全屏软件输入正确的密码才能退出。

ArchLinux 下的屏幕背光恢复

最近发现我的 ArchLinux 每次解锁之后屏幕背光都会设置为最大，今晚终于有时间把它修复了。 写这篇文章介绍在 ArchLinux 下开机（Boot）和解锁（Resume）时，如何恢复此前的屏幕背光。 先解释背光控制的机制，再给如何入配置和调试。 本文以 MacBook Pro 2013 Late 为例（intel 显卡，xf86-video-intel 驱动）。

本文只解决背光恢复的问题，如果你的 Fn 功能键无法调整背光，请参考 在 MacBookPro 上安装 ArchLinux 中的“显示器/键盘背光”一节。

龙胆虎威中的四加仑水迷题（Die Hard 3）

龙胆虎威 3 中的一个场景：在泉水旁有两个瓶子，容量分别是 5 加仑和 3 加仑。 Bruce 需要在 5 分钟内精确地得到 4 加仑水来停止定时器，差一盎司都会引起爆炸。 本文对这个问题进行推广，分别讨论有解的条件和解的构造两个问题，再给出判断是否有解的简单方法：能否被公约数整除。

如果目标水量 c 是 a 和 b 的线性组合就有解，否则无解。具体地：

1. 得到的水量一定是 a 和 b 的线性组合。即如果 c 不是 a 和 b 的线性组合就无解。
2. 重复地从 a 倒入 b，就可以得到 a 和 b 的所有线性组合。即只要是线性组合就有解。

c 是否是 a 和 b 的线性组合，取决于 c 能否被 gcd(a,b) 整除：

1. gcd(a,b) 是 a 和 b 最小的正的线性组合。
2. gcd(a,b) 能整除 c 等价于 c 是 a 和 b 的线性组合。

为方便讨论，本文所有线性组合都指整数线性组合，所有数字 x、y、m、n 都表示整数。

ArchLinux 键盘映射：交换 CapsLock 和 Ctrl

笔者在几个月前 切换到 Linux 下干活，使用 Xmodmap 交换掉 CapsLock 和 Ctrl。 但 Xmodmap 只能改键无法区分是哪个键盘硬件设备（偏偏 HHKB 的 Caps 本来就在左边），而且只在 X11 下好使（Virtual Console 下不起作用）。 于是近日研究了下 scancode 到 keycode 映射，通过 udev 匹配和配置特定的输入设备。 Harttle 的环境是 Macbook 下的 ArchLinux，下面的命令以此为例，但其他环境也应该类似。

注意：本文只讨论如何重新定义个别键的 keysym 的问题。更改键盘布局请参考 kbdmap，更改快捷键请使用 xbindkeys 或 i3 bindsym 或你的桌面系统配置。

保存和恢复 TMUX 工作区 —— The Easy Way

Harttle 此前介绍过 Tmux 的使用，我们知道 Tmux 可以把所有打开的 Shell 都保存在服务器。 你的 Terminal 重启不会丢失任何东西，但 Server 重启后 Session 会全部丢失。 如果你像 Harttle 一样在开发 PC 本地运行 Tmux Server 的话，每次开机后都需要重新建立各种会话和窗格。

本文介绍一个 Tmux 插件：tmux-resurrect， 可以一键保存当前 Tmux 状态，包括 Session、Window、Pane 布局，甚至 Vim 状态也可以恢复。

如果你更偏向 The Hard Way，可以参考 恢复 TMUX 工作区 - The Hard Way，手动完成一切初始化工作。

Vim、Tmux、系统共用剪切板

在 Tmux 终端复用 中介绍过 Tmux 的使用， 当你同时有系统剪切板、Tmux Clipboard、Vim Yank Buffer 时互相拷贝是不是很困难？ 本文介绍如何让它们共用一个剪切板。