KeBlog

折腾了大半天，终于在本机搭了一个功能完备的服务器。
当然要记录一下啊。
不过这是搭建成功后的总结，可能有地方遗漏，有问题欢迎提出来。

静态页面博客

这个用 hexo 和 jekyll 直接就可以做到，本地跑 server 不成问题，
比较 easy ，不赘述，详见 hexo 或者 jekyll 的官网。

动态页面博客

动态页面要能跑 php ，有数据库。

apache

这里用 apache(httpd) 搭建服务器：

1

sudo pacman -S apache2

执行 sudo httpd 后打开 localhost ，就有一个东西了（虽然是空的）。
在 /srv/http/ 下新建 index.html 随便写点东西，是可以显示的。
路径具体查看 httpd -S 。

启动服务：

1

sudo systemctl start httpd

php

安装 php （ manjaro18.x 预装了 php7.x ，但还是要一些其他的东西）：

1

sudo pacman -S php php-apache php-fpm

这时 apache 还是不支持 php 的，需要在配置里加上几行。
打开 /etc/httpd/conf/httpd.conf ，加入：

1
2
3
4

LoadModule php7_module modules/libphp7.so
AddType application/x-httpd-php-source .phps
AddType application/x-httpd-php .php
DirectoryIndex index.php index.html index.htm

开启 php 服务：

1

sudo systemctl start php-fpm

编写 index.php 试试，也可以运行了。 如果出了问题，找到配置里的

1

LoadModule mpm_event_module modules/mod_mpm_event.so

改成（应该就在下面被注释了）

1

LoadModule mpm_prefork_module modules/mod_mpm_prefork.so

mysql

我跑 mysql 的服务会卡死，不知道为什么，
所以我用 mariadb （mysql 的一个衍生似乎是）替代。

安装：

1

sudo pacman -S mariadb mariadb-client

初始化（注册一个账号）：

1
2

sudo mysql_install_db --user=mysql --basedir=/usr --datadir=/var/lib/mysql
sudo mysql_secure_installation

启动服务：

1

sudo systemctl start mysqld

试试能不能登上：

1

mysql -u<用户名> -p

让 php 支持 mysql 的调用，在 /etc/php/php.ini 找到 ;extension=mysqli 把分号去掉就行了。

使用 wordpress

Typecho 用 php7.2 似乎安装会出问题，
还是建议用 wordpress ，更加成熟，
安装方式在 wordpress 官网上把包下下来解压到 /srv/http/ ，
回了正常运行，需要改变 /srv/http 的权限，让 wordpress 能够对其做出修改。
这里不赘述，嫌麻烦可以 chmod 777 -R /srv/http 。

然后进入 localhost 按照步骤来就行了。

吐槽

一天普及一天省选，弄到一起就出成了一套提高组试题。

Day1

原题大作战。 然而我一题都没做过。

总的来说 Day1 比去年好像容易点（不然我也不会留出一个多小时给每道题造数据对拍）。

T1

CCF 直接把 2013 的题原封不动搬到了 Day1T1 。

一开始想着递归，发现会被卡成 $O(n^2)$ ， 再想 DP 的时候简化一下式子就直接可以扫一遍出结果。

T2

bzoj 权限题。

如果一种货币能被其它若干货币代替，就扔掉。 设 f[i] 表示价值为 i 的货币是否会被代替，做一遍完全背包就好了。

T3

bzoj 权限题。

听说可以二分加贪心，不过我考场想的比较复杂 是二分答案再 DP ，DP 转移再套一层用链表维护的 DP 。

首先容易想到二分答案，二分一个答案 mid 后求最多可以有多少条赛道满足长度不小于 mid ， 若有不少于 m 条，则答案可行。

求赛道数量可以 DP ，设 f[u] 为 u 的子树中满足条件的赛道的数量， g[u] 表示在满足 f[u] 最大的前提下 u 向下不经过赛道的最长路径长。

转移的时候先把 u 的儿子 v 的 f[v] 累加，同时将所有 g[v]+w 存起来（w 表示 u 到 v 的长度）。

对于 g[v]+w 大于等于 mid 的直接把 f[u]++ 然后扔掉，于是只需要考虑小于 mid 的 g[v]+w 的贡献。

两个不同的 g[v]+w 若大于等于 mid 就同样可以作为一条赛道让 f[u]++ ，先排序然后再次 DP 统计这样的赛道数量， 然后若所有的 g[v]+w 都有另外一个构成赛道， g[u]=0 ，否则 g[u] 等于剩下的最大的 g[v]+w 。

Day2

Day1 的比赛对我造成了巨大的影响，Day1 考完后信心爆棚， 以 AKIOI 的自信 走进 Day2 考场。

结果什么题都死磕正解，到最后连暴力都没打全。

看题，WTF?

看完 T1 我以为是个稠密无向图，想了好久感觉是要求一种特殊的生成树，感觉巨不可做。 顿时有点小慌，突然想到考前教练提醒要看完题，说不定后面的题反而简单。

嗯，有道理，直接翻到 T2 ，推了波结论认定是一道状压 DP，松了口气。

不急，再看 T3 ，哦，好像树形 DP ，但是 m 个询问难住了我。

于是认定 T2 比较容易，开始死磕 T2 ，打完状压后跑了遍 2,2 的样例，诶过了。 再跑一遍 3,3 ，输出 144 ，于是手推了 3,3 的样例发现还是 144 , 意识到推的结论有误，瞬间慌的一批。 推了好久才发现了问题，得到正确的结论后发现对于新结论状压 DP 似乎变得不可行。

这个时候考试已经过了一个小时多了。慌。

换换思路吧，于是去做 T3 , 想了很久 DP 最后写了个平方复杂度的， 跑过了所有样例就没管了，没多少时间了，又回去看 T1 。

往回看了看 T1 里 m 的数据范围我才发现只有树和换套树两种情况。 那还求个鬼生成树，迅速打掉树的 60 部分分，n 看都没看只知道 $O(n)$ 稳了。 再去想换套树，感觉差不多，继续 $O(n)$做。

结果？一直死磕 T1 的 $O(n)$ 做法，直到最后考试结束都没写出来。

考试听别人说直接枚举删边 $O(n^2)$ 就可以过的时候我才意识到 n 只有 5000 ，整个人懵的。

结果 T1 还是 60' ，T3 不晓得哪里炸掉了爆零， 有意思的是 T2 我错误的打法样例都没过在 ccf 的数据里水到了 45' 。

NTT ，快速数论变换，功能与 FFT 完全一致，用来求多项式卷积。
NTT 优点在于常数稍微小一点，没有精度误差。
但是 NTT 系数必须是取模意义下的整数，且对模数有特殊要求。

FFT 的单位根

建议前置 FFT 。

FFT 可以分治优化复杂度的原因是用到了单位根的如下性质：
$$W_{2n}^{2k}=W_n^k$$ $$W_n^n=1$$ $$W_n^{k+n/2}+W_n^k=0$$

可是用单位根做 FFT ，需要用到复数和浮点数，常数大而且有精度误差。
还有别的数有这样的性质来替换单位根吗？
遗憾的是，可以证明复数域下只有单位根有这样的性质。

取模

实际计算多项式卷积时，常常要求对系数取模以避免不必要的麻烦。
那么这时候系数实际上是在模意义下的， FFT 将它转到复数域上运算，似乎没有必要。
模意义下什么数可以有单位根那样的性质？
有的，那就是原根。

原根

对于某些模数 P ，模 P 意义下的原根 g 满足：
对任意 $0kP-2$ ， $g^k$ 互不相同。 有些模数可能不存在原根，这里先假设模数都有原根。

假设系数是模 P 意义下的，P 是形如 $2^k+1$ 的质数，其原根为 g ，
设 $G_n=g^{}modP$ ，其中 n 是小于 P 的 2 的整次幂 。
那么在模 P 意义下， G 满足：

$$G_{2n}^{2k}=G_n^k$$

由 G 定义可证：
$G_{2n}^{2k}=g^{2k}=g^k=G_n^k$

$$G_n^n=1$$

由 G 定义可得：
$G_n^n=g^n=g^{P-1}$
由费马小定理：
$G_n^n=g^{P-1}=1$

$$G_n^{k+n/2}+G_n^k=0$$

有第一条性质可得：
$G_n^{n/2}=G_2^1=g^{}$
因为 $ (g^{})2 = g^{P-1} = 1 $根据原根的性质：$ g^{} g^{P-1} $那么$ g^{} = -1 $（即P-1）。那么可以证得：$ G_n^{k + n/2} = G_n^k G_n^{n/2} = G_n^k(-1) $于是$ G_n^{k + n/2} + G_n^k = 0 $

NTT

于是 NTT 的算法思路就呼之欲出了：把 $W_n$ 全部替换为 $G_n$ 即可。
这样就可以算出模 P 意义下的多项式卷积了。
其中 n 必须是 2 的整次幂，不足的补零即可。

现在唯一的问题是，模数 P 要满足什么条件，以及如何求模 P 意义下的原根 g 。
然而我并不想深入展开，大多数情况下模数都是 998244353 ，其原根为 3 。
一般 NTT 只会用这个模数，不会有毒瘤出题人卡这个模数的（我不对这句话负责）。

历程

• 最先用的是 Ubuntu 16.04 自带的 Unity 。
• 更新 Ubuntu 后用的 Ubuntu 18.04 自带的 Gnome 。
• 用了 Gnome 后学会了折腾，各种配置堆上。
• 后来发现 Gnome 太卡太吃内存，并且才知道系统可以换桌面， 于是在 master 安利下换上 xfce 。
• xfce 很稳定很流畅，但是太丑，可玩性太低，于是换上高大上的 KDE 。
• 中途还换过 enlightenment ，但是 enlightenment 的稳定性实在不敢恭维。
• 最后用上了 i3 ，原因不详。

WARNING:
既然你打算尝试 i3 ，本文假设你有一定的动手能力（说白了就是能折腾）。

安装

sudo aptitude install i3-wm 后注销重进选择 i3 即可。

然后你会发现弹出个窗口，接下来黑屏，没有动静。
WTF ?
其实 i3 已经开了，只是没背景而已，按 win+Enter 打开终端。

配置

弹出一个菜单给你设置？想多了，要配置就写 ~/.config/i3/config 去吧。

$mod是i3的灵魂，每一个快捷键最好都以$mod 开头，
一般 $mod 被设置成 Mod4 ，也就是 Win 键。
bindsym 是绑定快捷键，注释很详细，自己看，下面列出一些重要的配置。

方向

i3 默认把 jkl; 做方向键，也许你会更喜欢 hjkl ，自己替换掉就是了。
另外分号不是 ; 而是 semicolon 。

壁纸

i3 默认没有壁纸，因为它是个平铺式的窗口管理器。
但壁纸是第一生产力啊，不要壁纸怎么行。

下载 feh: sudo aptitude install feh.
feh --bg-fill (YOUR_IMG) 就可以设置壁纸了，至于实现原理，你不会想知道的。

锁屏

i3 默认没有锁屏，为了防机惨，锁屏还是很有必要的。

下载 i3lock: sudo aptitude install i3lock.
直接 i3lcok 就可以锁屏，i3lock -i (YOUR_PNG) 还可以设置锁屏壁纸。
需要快捷键锁屏的话，加上一句配置就行了：

1

bindsym $mod+Tab exec i3lock # Win+Tab 锁屏

工作区

i3 对工作区的数量没有限制，工作区的名字甚至可以有字母。
i3 默认配置里只提供了切换到 1 至 10 的快捷键，
但是有时候“切换到下一个工作区”和“切换到上一个工作区”可能更方便。
加上两句：

1
2

bindsym $mod+comma workspace prev # Win+逗号
bindsym $mod+period workspace next # Win+句号

另外，默认配置里，把一个窗口移动到某工作区的时候仍会停留在原工作区，
想改变这点， 把 move container to workspace x 后面加上 ; workspace x 即可。

i3bar

个人超喜欢 i3bar ，因为它可以接受任何一个程序的输出。
这意味着你可以完全自由地定制 i3bar 。

找到 bar { 这行。
bar 的模式有三种：

1
2
3

mode hide # Auto display
mode invisible # Never display
mode dock # Alway display

位置有两种：

1
2

position top
position bottom

重点来了，定义处理程序这一项：

1

status_command i3status

可以看到默认使用 i3status 作为处理，i3status 本身也可以配置，
但是如果想自由配置，你可以写个程序，输出一个 json ，接口比较复杂，
在此不赘述，你可以在 ~/.config/i3status/config 里加几行：

1
2
3
4
5

general {
	   output_format = "i3bar"
	   colors = true
	   interval = 5
}

再运行 i3status 依葫芦画瓢就是了。

i3-gaps

如果你希望窗口平铺之间会有间隙，i3-gaps 会满足你。
如果你用 Debian, Ubuntu ， 去 github 上搜 i3-gaps-deb clone 下来后运行 i3-gaps-deb 就行了。
如果用 Arch ，软件包管理器里有，直接下。

透明

也许你给终端模拟器设置了透明度，很遗憾，在 i3 上没用。
解决方案是下载 compton ，运行 compton -b 即可。

接口

你可以很自由地向 i3 发送命令，i3-msg 提供了一系列接口，
足以帮助完成更复杂的定制。

使用 i3-input 可以直接向 i3 发送一条命令。

折腾了半天 i3lock ，不写篇博客可惜了。

i3lock 有啥好折腾的？不就是挂个壁纸锁屏嘛。
就是因为 i3lock 太鸡肋了折腾啊。
于是我试过了 i3lock 的各种民间 fork 版本，在此总结。

i3lock

官方版本 i3lock ，稳定可靠，但是鸡肋。

安装：

1

sudo aptitude install i3lock

使用：

1

i3lock

i3lock-lixxia

最友好，最简单的一个 i3lock fork ，
优化了中间显示的圆形框，并支持一些颜色自定义。

安装：

1
2
3
4
5
6
7
8

sudo aptitude remove i3lock
sudo aptitude install pkg-config libxcb1-dev libxcb1 libgl2ps-dev libx11-dev libglc0 libglc-dev libcairo2-dev libcairo-gobject2 libcairo2-dev libxkbfile-dev libxkbfile1 libxkbcommon-dev libxkbcommon-x11-dev libxcb-xkb-dev libxcb-dpms0-dev libxcb-damage0-dev libpam0g-dev libev-dev libxcb-image0-dev libxcb-util0-dev libxcb-composite0-dev libxcb-xinerama0-dev
git clone https://github.com/Lixxia/i3lock.git
cd i3lock
autoreconf -fi
mkdir -p build && cd build
../configure
make && sudo make install

顺带一提，只有这个 fork 给出了靠谱的源码安装方式，
其他 fork 甚至 i3lock 本身的安装方式都给得很不靠谱。

使用：

1

i3lock

i3lock-blur

支持模糊背景，毛玻璃特效。

安装：

1
2
3
4
5
6
7
8

sudo aptitude remove i3lock
sudo aptitude install pkg-config libxcb1-dev libxcb1 libgl2ps-dev libx11-dev libglc0 libglc-dev libcairo2-dev libcairo-gobject2 libcairo2-dev libxkbfile-dev libxkbfile1 libxkbcommon-dev libxkbcommon-x11-dev libxcb-xkb-dev libxcb-dpms0-dev libxcb-damage0-dev libpam0g-dev libev-dev libxcb-image0-dev libxcb-util0-dev libxcb-composite0-dev libxcb-xinerama0-dev
git clone https://github.com/karulont/i3lock-blur.git
cd i3lock-blur
autoreconf -fi
mkdir -p build && cd build
../configure
make && sudo make install

再顺带一提，只有这个 fork 直接给出了需要安装那些库。

使用：

1

i3lock --fuzzy

i3lockr

支持模糊背景，毛玻璃特效。

安装：

1
2

wget https://github.com/owenthewizard/i3lockr/releases/download/v1.0.0-final/i3lockr
sudo mv i3lockr /usr/local/bin

使用：

1

i3lockr --blur=25

i3lock-color

对于颜色的自定义十分全面。

安装：

1
2
3
4
5
6
7
8

sudo aptitude remove i3lock
sudo aptitude install pkg-config libxcb1-dev libxcb1 libgl2ps-dev libx11-dev libglc0 libglc-dev libcairo2-dev libcairo-gobject2 libcairo2-dev libxkbfile-dev libxkbfile1 libxkbcommon-dev libxkbcommon-x11-dev libxcb-xkb-dev libxcb-dpms0-dev libxcb-damage0-dev libpam0g-dev libev-dev libxcb-image0-dev libxcb-util0-dev libxcb-composite0-dev libxcb-xinerama0-dev
git clone https://github.com/PandorasFox/i3lock-color
cd i3lock-color
autoreconf -fi
mkdir -p build && cd build
../configure
make && sudo make install

使用：

1

i3lock

i3lock-fancy

重头戏，star 最多的 fork ，甚至比 i3lock 本身更多，被广泛使用。

安装：

1

sudo aptitude install i3lock-fancy

使用：

1

i3lock-fancy

依赖 i3lock ，实际上是产生了背景图片再调用 i3lock 。
默认使用模糊背景，用起来没什么问题，但是事实上，
圆形框的颜色并不是最正确的，而是兼容的。

源码里有这样一条：

1
2
3
4
5

# try to use a forked version of i3lock with prepared parameters
if ! i3lock -n "${PARAM[@]}" -i "$IMAGE" > /dev/null 2>&1; then
    # We have failed, lets get back to stock one
    i3lock -n -i "$IMAGE"
fi

bash -x i3lock-fancy 就知道，
if 上的命令往往失败了，执行的是 if 里头的命令。

事实上这需要 i3lock-color 。
那么，安装 i3lock-color 代替 i3lock 后，执行 i3lock-fancy ，
会发现圆形框的颜色与背景更加配了。

关于模糊背景

事实上，如果你用了 compton 再用 i3lock ，效果十分差劲。
解决这个方案，可以在调用 i3lock 前 kill compton ，结束后重新启动 compton 。

拿 i3lock-fancy 举例，把之前展示的代码改成这样：

1
2
3
4
5
6
7

# try to use a forked version of i3lock with prepared parameters
pkill compton
if ! i3lock -n "${PARAM[@]}" -i "$IMAGE" > /dev/null 2>&1; then
    # We have failed, lets get back to stock one
    i3lock -n -i "$IMAGE"
fi
compton -i 0.8 -b

其次，用模糊背景通常会比较慢，尤其是 i3lock-fancy ，需等上 3 秒左右。
那么如果调用 i3lock-fancy 之后你又做了一些别的操作，比如关闭一个窗口，
这时锁屏了，你会发现背景和原来的不一样。 :)

ncurses 是基于终端的十分强大的图形库。 Vim, screen, sl 等终端程序都用到了这个库（足以见其强大）。

安装

部分系统默认安装了 ncurses ，手动安装的方式是： sudo aptitude install ncurses-dev 。

使用的程序需要 #include <ncurses.h>　。 编译时需要添加 -lncurses 参数进行链接。

开始和结束

调用 initscr 初始化窗口，endwin 结束窗口。

1
2
3
4

#include<curses.h>

WINDOW *initscr(void);
int endwin(void);

输出

调用 initscr 后调用 endwin 前，printf, std::cout 等标准输出不会显示在屏幕上。 而输出到屏幕上需要 ncurses 提供的相应函数。

函数

1
2
3
4
5
6
7
8

int addch(const chtype char_to_add);   // 当前位置添加字符
int addstr(const char *string_to_add);    // 当前位置添加字符串

int printw(char *format, ...);   // 类似于 printf
int refresh(void);    // 强制刷新物理屏幕

int beep(void);   // 终端响铃
int flash(void);   // 屏幕闪烁

输入

调用 scanf, getchar, cin 等标准输入函数同样无效。

函数

1
2
3
4
5
6
7
8
9
10

int cbreak();   // 字符一键入，直接传给程序（不用按下回车）
int nocbreak();  // 关闭 cbreak

int echo(void); // 开启输入回显
int noecho(void); // 关闭输入回显

int getch(void); // 读入一个字符
int scanw(char *format, ...); // 类似于 scanf

int clear(void); // 清屏

输入函数通常是阻塞的，但是通过调用 nodelay(stdscr, TRUE); 可以关闭阻塞。 此时若输入函数未读取到内容会返回 ERR 。

光标

控制光标。 调用 initscr 后调用 endwin 前，输出终端控制符改变光标是无效的。

函数及示例

1
2
3
4
5
6
7
8
9
10
11

int move(int x, int y); // 将光标移动到 [x] 行 [y] 列，左上角为 0 行 0 列

int curs_set(int visiblility); // 参数为 0 表示隐藏光标，1 表示显示光标

int getyx(WINDOW* win, int &x, int &y); // 获取指定窗口光标位置，示例如下

void move_up() { // 将光标上移
	int x, y;
	getyx(stdscr, x, y); // stdscr 表示标准屏幕
	move(x - 1, y);
}

指定位置输出

在指定位置输出不必先 move 再 printw ， ncurses 提供了 mv 函数前缀在指定位置输出。 例如 mvprintw(1, 2, "%d", 2) 在 1 行 2 列输出 3 。 类似的有 mvaddch, mvaddstr 等。

颜色

初始化

首先需要调用 has_color() 查看当前运行环境是否支持彩色。 调用 start_color() 初始化颜色，成功则返回 OK 。

1
2

bool has_colors(void);
int start_color(void);

成功后会初始化全局变量 COLORS 表示终端支持的颜色数量 还会有 COLOT_WHITE, COLOR_RED 等 8 个表示颜色的变量。

使用

例如希望打印白底黑字的信息：

1
2
3
4
5
6
7
8
9

void print(const char *info) {
	init_pair(1, COLOR_BLACK, COLOR_WHITE);
		// 的一个参数表示编号，后面两个分别表示字体和背景颜色
	attron(COLOR_PAIR(1));
		// attron 是一个设置函数，COLOR_PAIR 返回指定编号的颜色信息
	addstr(info);
	attroff(COLOR_PAIR(1));
		// attroff 关闭设置（若接下来需要用其他颜色可以不调用 attroff 而直接使用 attron 覆盖设置
}

错误示例

值得注意的是，必须保证 init_pair 的编号不与其他已初始化的编号重复 一个错误的调用如下：

1
2
3
4
5
6
7

const char *info = "ERROR CODE";
init_pair(1, COLOR_BLACK, COLOR_WHITE);
attron(COLOR_PAIR(1));
addstr(info); // 打印白底黑字
init_pair(1, COLOR_BLACK, COLOR_RED);
attron(COLOR_PAIR(1));
addstr(info); // 打印白底红字

上述代码的期望打印出白字和黑字两种不同的颜色， 但事实上只会打印出红色一种。 解决方案便是将白底红字的 pair 编号设为 2 。

窗口

ncurses 有窗口类 WINDOW 并提供了 stdscr 作为默认窗口。 有时一个窗口无法满足需要，此时需要自己新建窗口。

新建窗口

调用 newwin 来新建窗口。

1
2

// 从 ([x], [y]) 开始新建 [line] 行 [column] 列的窗口。
WINDOW *newwin(int line, int column, int x, int y);

新建的窗口

通用输出

addch, printw 等输出方式只输出到 stdscr 。 ncurses 提供了 w 前缀来输出到指定窗口。 例如 wprintw(win, "%d", 1) 在 [win] 窗口输出 1 。 但是自己新建的窗口与 stdscr 不同， 若想在屏幕上显示需要调用 wrefresh(win) 刷新窗口。

若想在窗口中指定位置输出，可以用 mvw 前缀函数。 例如 mvwprintw(win, 1, 2, "%d", 3) 在 [win] 窗口的 1 行 2 列（ 相对位置 ）输出 3 。

子窗口

调用 subwin 创建子窗口。

1
2

// 从 ([x], [y]) 开始新建 [line] 行 [column] 列属于 [parent] 的子窗口。
WINDOW *subwin(WINDOW *parent, int line, int column, int x, int y);

子窗口与普通窗口的区别在于它与其父窗口共用屏幕储存空间， 子窗口修改时父窗口会直接受到影响。 比如新建了 stdscr 的子窗口 win ， 那么输出到 win 后想显示在屏幕不调用 wrefresh 而是调用 touchwin(stdscr) 。 touchwin 用于标记一个窗口被修改。

销毁窗口

调用 delwin 销毁窗口。

1

int delwin(WINDOW *win); // 销毁 [win] 窗口

窗口销毁后其在屏幕上对应的内容不会改变。

离开

有时候可能需要离开 ncurses 回到行缓冲模式做些事情而且需要在之后回到 ncurses 。 例如 Vim 里面输入 :!ls 就会退出 ncurses 运行 ls 命令，并在用户敲下回车后回到 ncurses。

调用 def_prog_mode 暂存，调用 reset_prog_mode 恢复。

示例

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

int main() {
	initscr();
	printw("Hello World !!!\n");
	getch(); // 等待用户输入
	def_prog_mode(); // 存储当前tty 模式
	endwin(); // 退出 ncurses 模式
	system("sh"); // 返回普通的行缓冲模式
	reset_prog_mode(); // 返回到 def_prog_mode() 存储的 tty 模式
	refresh(); // 刷新屏幕（必须！）
	getch(); // 等待用户输入
	endwin(); // 退出 ncurses 模式
	return 0;
}

输出中文等非 ASCII 字符

事实上 ncurses 并不支持直接输出中文， 这意味着调用 printw("中文") 会是一堆乱码。 解决方案如下：

安装库

这需要另一个库。 通过 sudo aptitude install libncurses5 libncursesw5 libncursesw5-dbg libncursesw5-dev 安装

头文件

一定是 #include <ncurses.h> 而不是 #include <curses.h> 。 另外在 main.cpp #include <locale.h> 。

调用

在调用 initscr() 之前 调用 setlocale(LC_ALL, "") 。

编译

将 -lncurses 参数改为 -lncursesw 。

sl / LS

在你 ls 打累的时候开小火车。

安装方式

1

sudo aptitude install sl

lolcat

用彩虹为输出着色！

示例

安装方式

1
2

sudo aptitude install rubygems
gem install lolcat

管道处理

非常有意思的是，将大多数 ncurses 程序的输出通过管道用 lolcat 后仍然可以正常运行！

比如 nano | lolcat 可以打开一个彩虹编辑器；
ncdu | lolcat 可以打开一个彩虹文件查看器；
sl | lolcat 可以开彩虹火车；
nethack | lolcat 可以玩彩虹游戏！

cowsay

让一只奶牛（或者其它乱七八糟的东西）说出一句话！

示例

运行 cowsay hiahiahia

然后你会得到像这样的输出：

 ___________
< hiahiahia >
 -----------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

类似的你也可以用 cowthink 。

安装方式

1

sudo aptitude install cowsay

chafa

在终端里面打印图片或者视频！

示例

小诀窍：把终端字体调小并开全屏可以让图片更清晰（但是更慢）。
给你一图片自行意会（记住这张图是在终端上打印的！！！）：

安装

1
2
3
4
5

git clone https://github.com/hpjansson/chafa.git && cd chafa
sudo aptitude install libmagickwand-dev
./autogen.sh
make
sudo make install

这个安装过程相对比较麻烦，详细过程见 Github 。

img2txt / cacaview

在终端里用 ASCII 打印图片！

或者用 cacaview 打开一个窗口查看。

upd: 后来我才知道 w3m 也可以查看图片，和 cacaview 的效果一模一样。

安装

1

sudo aptitude install caca-utils

w3m / lynx / browsh

在终端浏览网页！

示例

w3m 和 lynx 大同小异，没有什么本质上的区别。 （别喷我，我这么说是拿 browsh 作参照）

但是， browsh 不同，它内部调用 Firefox 渲染网页并处理后打印在终端， 因此 browsh 几乎能 在终端 支持任何现代浏览器支持的！

只给出一张 browsh 浏览 youtubu 的图片：

安装

1
2
3
4
5
6
7

# w3m
sudo aptitude install w3m
# lynx
sudo aptitude install lynx
# browsh
wget https://github.com/browsh-org/browsh/releases/download/v1.5.0/browsh_1.5.0_linux_amd64.deb
sudo dpkg -i ./browsh_1.5.0_linux_amd64.deb

cmatrix

终端黑客风动画

cmatrix | lolcat 简直可以来当屏保。

安装

1

sudo aptitude install cmatrix

typespeed

在终端 玩打字游戏 测试打字速度！

示例

安装

1

sudo aptitude install typespeed

自定义词库

我是真的爱折腾，竟然自己找出了 typespeed 的词库位置并且自己加了词库。。。

顺便夸一下 typespeed 的扩展性真的好，它考虑到了用户的自定义词库需求。

只需要在 /usr/share/typespeed/words/ 目录下添加 words.xxx 文件（ xxx 随意填），
文件第一行是这个词库的名称，接下来每行一个单词就可以了。

然后进入 typespeed 就能看到你自己的词库啦（ kewth's xxx 就是我自己加的）：

nethack

世界上最棒的终端游戏（绝无夸大）！
nethack 太博大精深了，玩法不赘述。

另外： nethack | lolcat 的效果真的很棒。

安装

1

sudo aptitude install nethack

task

全名 taskwarrior 。

个人认为终端上最好用的 todo list manager 。
功能十分强大，可以简单上手，
如果愿意折腾也可以深入挖掘它的各种功能，最精细地管理你的任务计划。

安装

1

sudo aptitude install taskwarrior

简单上手

1
2
3
4
5
6

task add test1
task add test2
task start 1
task long
task done 1
task done 2

tasksh

整合 taskwarrior 的交互命令行，里面可以直接敲 add ... 或 list 等命令。

Q: 我天天盯着你高考 (gq) 怎么一直没更新啊？
A: 懒。

因此这实际是一篇事后回忆。

Day0

昨天晚上特意没去学校回了家，想着离高铁站近可以晚点起床，
真相是需要回家拿电脑
然而大早上 6 点就被叫了起来，早餐都没吃就直接送到了高铁站，
emm 还有大半个小时才检票，果断拿起颓书开始颓废，
不要问为什么不玩电脑，心塞。

高铁上还是贼无聊，幸好准备了颓书，
而且还可以蹭旁边的人看《生活大爆炸》。
还行，比上次去安徽好得多。

出高铁再做地铁去北大，北京地铁线比长沙多得多，
全程没搞清往哪走，迷迷糊糊地跟别人跑。
下了地铁第一反应就是，热，真热，贼 NM 热，
地理菜狗还以为北京纬度高就会比较凉快来着。

至于住的酒店，我敢说这是我住过最差的酒店了，
整一偏僻平房（有点像四合院？），里面要啥没啥，
卫生条件极差，听隔壁德拉说他们床头粘了 10+ *** ，部分带红，估计是 **** 。
水龙头都 tm 生锈了，淋浴喷头竟然对着马桶。
之前住安徽时还喷了那宾馆来着，现在感觉那简直是天堂。

晚上还是很 nice 的，上一届北大的信息组学长们请我们吃饭，
特意选了一家比较符合湖南人口味的饭馆，
吃完饭后被拉到北大到处乱转，
北大确实很漂亮，晚上没什么灯，不是灯火通明的那种喧嚣繁华，比较安静，
还有未名湖，不敢随便形容，不过听说每年都有人不小心掉下去。

Day1

上午的开幕式已经忘了讲了什么了，
大概是大谈信息学发展，北大的优势和竞赛生在北大的学习方向。

北大食堂贼多，不过我们可以吃的只有三个，农园最近，大家就都去了农园，
还不错，至于消费我跟本没注意，反正看到还行的就拿了。。。发的 100 元的卡应该够用的。

下午的考试，萎出天际，可能是没有找到状态吧，
三道题目一点思路都没有，真的就是只想得到暴力，还是最暴力的暴力，
结果暴力还打挂了，明明过了样例过了自测数据，但是就上去就是使劲 WA 。
正常考试处于崩溃和半放弃的状态，最后得到了 18' 的好成绩。

本来挺乐观的，以为和省选一样，大众分就是几十分，
然而问了一波成绩发现某 Jian 200+ 。。。
好吧是我凉了。

于是颓了一晚上，打 generals ，看敖厂长，本来想打饥荒然而被我的 XP 折服了。

Day2

上午大师讲座 master 牛逼 ，请的外国的一位教授，图灵奖获得者。
这次讲座我感触很深，受益匪浅，得到了一个教训和今后的一个小目标：
好好学英语。
woc 英语菜狗全程懵逼啊，除了黑板上画的图什么都搞不懂。
讲完后还有学生提问题的环节，看着别人和教授谈笑风生，对我就加密了一样。

《论常规课的重要性》

下午考试心态比较佛，已经清楚翻盘无望了，
看了三道题后只感觉有一题可做，题意大概是这样：

给定一颗 n 个点的树，将其放在 m 维空间里，
需要满足每两个点的曼哈顿距离与其在树上的距离相同。
求出一个使 m 最小的放置方案。

一个维度在树上只能管一条链，题目可以转换为最小链覆盖。
然而我考场上的转换方式不太一样，更复杂，每条链要去掉 lca,
于是我就搞了个 dfs 去求这玩意，交上去过了 subtask1 和 subtask3 。
woc? subtask3 是没有限制的，讲道理过了 subtask3 就一定可以过 subtask2 。
仔细分析发现 dfs 儿子的顺序会有影响，没想出来怎么去掉这个影响，于是开始操作。
我 dfs 的时候选择 size 最大的一个儿子去递归，再交，还是一样。
我 dfs 的时候选择叶子数最大的一个儿子去递归，再交，还是一样。
我 dfs 的时候随机选择一个儿子去递归，再交，过了 subtask1 和 subtask2 。
Nice 啊综合一下呗，根据输入数据特判一下，如果是 subtask2 就随机递归，subtask3 就自然递归。
成功 AC ，最后 122' 。

晚上贼颓，因为明天不用考试嘛，于是爆肝小游戏，都是颓过的人，细节自己想都想得出。

Day3

闭幕式。

出题人出来讲题了，果然是吉司机（和另外一个不知名人士），
题面中全是“九条可怜是个爱...的女孩子”。
但正如他本人所说，这次的确没有什么麻将啊斗地主啊之类的题，
整体偏向思维，没有毒瘤数据结构，没有大模拟。
好吧回想起来比赛质量确实很好，可能在吉司机画的那个图像的最高点附近吧。

颁奖的时候就只能看着了，连个安慰奖都没摸到，自闭了。

中饭进哥请食堂，吃完后就回去了，
高铁上巨颓，拷了两季生活大爆炸后直接开始追剧，
除了中间吃泡面外就没停（包括教练过来查水表）。
感觉被带进坑了。

常规快乐。

定义

简单来说，形如 $a_0+a_{1}X+a_2{X}^2+...+a_n{X}^n$ 的代数表达式叫做多项式， 可以记作 $P(X)=a_0+a_{1}X+a_2{X}^2+...+a_n{X}^n$ （系数表示法）， a 叫做多项式的系数，X 是一个不定元，不表示任何值， 不定元在多项式中最大项的次数称作多项式的次数。

加减

两个多项式 a, b 的和 a + b 是一个多项式 c ，满足： $x,c(x)=a(x)+b(x)$

两个多项式 a, b 的差 a - b 是一个多项式 c ，满足： $x,c(x)=a(x)-b(x)$

多项式的加减十分自然，实际运算中也只需要按定义 O(n) 枚举即可。

乘

两个多项式 a, b 的积 a * b 是一个多项式 c ，满足： $x,c(x)=a(x)b(x)$

此时将 a, b 的系数按分配率展开求 c 的时间复杂度为 O(n * m) ， n, m 分别为 a, b 的次数，不难得出 c 的次数为 n + m 。

快速求多项式乘积的方法是 $O(nlo{g}_{2}n)$ 的 FFT 或 NTT 。

除

两个多项式 a, b 的商 a / b 是一个多项式 c ，满足： $x,c(x)=a(x)/b(x)$

众所周知多项式除法可以列竖式求解， 这样做与乘法一样复杂度为 O(n * m) 。

取模

正如整数除法会有余数，多项式除法也不一定整除， 此时 a / b 会余一个多项式 c ， 正如整数除法中余数小于除数， 此处也要满足 c 的次数小于 b 的次数以保证唯一性。

具体来说，对于多项式 a, b 存在唯一的多项式 c, d 满足： a = b * d + c 且 c 的次数小于 b 的次数， 便称 c 是 b 除 a 的余数，即 a 模 b 的结果， d 是 b 除 a 的商。

值得注意的是，当模数 b 可表示为 $b(x)=x^k$ 时， a 模 b 相当于将 a 舍弃所有次数大于等于 k 的单项式的结果。

逆元

对于多项式 a ，其在 mod p 意义下的逆元 b 满足： a * b mod p = 1 且 b 的次数不比 a 大 （此处的 1 实际上是指只有常数项为 1 而次数为 0 的多项式）， a 的逆元通常记为 $a^{-1}$ 或 inv(a) 。

那么在 mod p 意义下，有 $a/b=a{b}^{-1}$ 。

逆元的求解

事实上模数一般是 $x^n$ 。

此时可以用分治求多项式 a 的逆元 b。

假设已经分治求得了 a 模 $x^{n/2}$ （此处及以下除法表示向上取整）的逆元 c 。 那么有： $$a\cdot c\equiv 1(mod{x}^{n/2})(1)$$ 由 b 的定义可知： $$a\cdot b\equiv 1(mod{x}^n)(2)$$ 转换为： $$a\cdot b\equiv 1(mod{x}^{n/2})(3)$$ (3) - (1) 得： $$b-c\equiv 0(mod{x}^{n/2})(4)$$ 两边同时平方得： $$b^2-2bc+c^2\equiv 0(mod{x}^n)(5)$$ 两边同时乘 a 得： $$b-2c+c^{2}a\equiv 0(mod{x}^n)(6)$$ 移项，整理： $$b=(2c-c^{2}a)mod{x}^n$$

4. -> (5) 中模数平方的原因： 左边多项式模 $x^{n/2}$ 为 0 代表该多项式每一项最低次数为 n / 2 + 1 。 那么该多项平方后最低次数会是 n + 1 或 n + 2 ， 模 $x^n$ 后仍为 0 。

于是乎分治，直到 n == 1 ，此时多项式的取模为一个常数，逆元也就是整数的逆元。

其中乘法使用 FFT ，则最终时间复杂度为 $O(nlo{g}_{2}n)$ 。

12 天的培（kao）训（shi），坚持每日总结。

Day0 to Day4.

Day0

大清早的就出发了，地铁还是那么挤。
先从长沙坐到南京，高铁上干坐 6 个小时贼贼贼贼贼无聊。

中午幸好提前买了泡面，随便应付一下，坐了一上午不动也不会感觉饿。
%%% 在高铁上一餐吃 70rmb 的 lzk 。

到了南京还得等 1 小时转到芜湖，期间 UNO 现学现玩，
第一把就赢了，一定是传说中的新手的欧气附体，
但是这欧气来得快去的也飞快，后面再也没赢过 ，并且一度成为全场最富（一次拿了 20 张牌也是没谁了）。

再到动车上就累了，睡了一觉。

宾馆感觉一般但也还行，位置不错，旁边就是美食街，
逛一遍发现芜湖的物价似乎比长沙要便宜得多？
这里奶茶只有长沙一半多的价格还巨好喝，还有木桶饭最便宜 8rmb, 最贵也 16rmb, 吃得相当饱，提供的辣椒酱好评。

晚上宾馆自习，我的笔记本实在实在实在是太 tm 旧了 windows xp 实在实在实在是忍不了啊。
宾馆的 wifi 都连不上去我怎么怎么打（kan）代（dian）码（ying）啊？？？
还有我早已练就一身折腾本领，小事，关掉 XP 的沙雕代理轻松解决。
但是网络实在是 suo （也许是我电脑不行？），努力了一晚上都没能成功看上电影。

Day1

第一天考试，凄惨爆 0 。
考试的时候想不出题啊（我太菜了），比较心不在焉，
才发现打满暴力都是一种困难，水平不够。
%　一 % 成功拿满暴力的 CZZ, orz 。

第一题维护区间历史最小和，玄学转换到二维平面 KD-Tree, 这玩意前几天刚考但是没去学，
我发现冷门算法一考就会连续考几次。

第二题一脸不可做，题目名叫因式分解，我也就真的只会因式分解了。
讲题的时候满分做法爆搜？？？好吧正解还是要个 DP 的。

第三题式子题妙啊妙啊，这什么用 ${}_{i=0}^{n-1}{A}^i=$ 把 $A^n$ 换掉的清奇思路谁想得到啊。
还有把 f(i) O(1) 一路推到 f(n) 再用组合数的奇技淫巧把 k 到 n 的枚举换成 1 到 k 谁想得到啊。

还有吐槽一下这套题部分分好少，几乎只有两档：暴力 -> 正解。

然后就是晚上的 自由欢乐时光 认真自习。
终于成功把昨天的电影看了一半。
然后颓了一晚上也是没救了，没办法 T3 被卡常心态爆炸（这就是你颓废的理由？）。

Day2

成功拿到预期的暴力分 30，一大进步。

第一题图染色，考场上脑子不清醒，很快想到 $O(n^2)$ 的建图方式后，
竟然完全没有想到怎么计数，最后 $O(n^n)$ 枚举染色方案可还行。
于是 40' -> 10'

第二题又是一个计数，AC 自动机？我完全没想到，
我还以为是容斥，但是发现有有 5 种情况，容斥起来要 5 + 10 + 10 + 5 种情况加加减减，
没敢打，不过这次这题部分分给的挺全的，分了 10 个 subtask 还是不错的 ~~虽然我只拿了 20 ~~ 。

第三题玄学最短路，要用最短路树（我想到了但是没啥用），这玩意前几天 czz 才讲，
果然又应验了我昨天说的，一考就连续考几次
暴力都很难打啊这题，到最后只能 puts("-1") 了，然而 subtask 数据捆绑。

一考完就被 *** 拉去吃什么网红烤冷面（然而是热的），very nice but 量有点少。
然后 *** 就拉了一堆人去星巴克 666 ，讲真这是我第一次在星巴克喝咖啡，忍痛剁手。
晚上到宾馆就开始颓，终于看完了昨天的电影 壮哉我大火影 。

Day3

今天的题目巨难，听出题人说是因为他明天赶时间所以把明天的 毒瘤 题全放今天就有更多时间讲。

第一题在 2 * n 的网格图上求一个生成树，我想到有个类似的题（求 2n 的网格图上放一颗树的方案数），
但是那道题我已经忘记怎么做了，而且那是计数，而这题是要求一个最优方案，
反正就是以为可做然而 Naive, 浪费了很多时间最后打了枚举生成树的大暴力。
考场上有一个线性计算当前方案的算法，枚举的时候加一点小剪枝，总复杂度应该是 $O(6^{n}n)$ ， 预计 20' ，但是实际上还是只有 10' 。

第二题感觉是什么数据结构题，我按照一种贪心思路敲了线段树，
估摸着有 23' 就没管了，后来出题人放了三个大样例，我一测，第一个就 WA 了，改了一点细节后过掉了，
再测第二个，又 WA 了，然后 debug 了好久才意识到贪心的思路不对，这个时候离考试结束只有 5min, 弃疗。
然后和预计的一样，3' 。

第三题是在一个很奇怪的图上面求最短路为 x 的点对（怎么又是最短路），
大暴力就是跑出每个点对的最短路再统计嘛，这个图发现了一些性质，但是还是不会做，
想着应该不难打就去打 T2 了，然后 T2 打到结束前 5min 所以这题的暴力也没打， 0' 。

今天的部分分还是很少，T2 T3 的暴力都只有 3' ，难受。

中午去一个东北菜馆吃饭，菜上的k慢但是挺好吃，很有特色，
最抢眼的是收银台前面的冰箱，里面一条巨大的鱼（完整一条的可能比我还大？）。

下午有洛谷月赛，于是冠冕堂皇地不改题打月赛，洛谷月赛一如既往，除了签到题都只能打暴力。

晚上险些被查水表，我正在听歌教练突然敲门，我当时就以迅雷不及掩耳盗铃儿响叮当仁不让世界感受痛楚汉相争之势拔掉了耳机。
没错，拔掉了耳机，然后 tm 就变成外放了声音贼大，当时就感觉自己真是沙雕了我去，
然后我又以迅雷不及掩耳盗铃儿响叮当仁不让世界感受痛楚汉相争之势插上了耳机（被自己秀死了），这个时候教练已经差不多进来了，然后交代一些事，我耳机就插在笔记本上光明正大地摆桌上，有点小可怕，还好教练没有说什么。。。

从今天开始教练晚上要强制收电脑，于是 10:30 电脑被收后无所事事，
这时候大家都要睡了（比如柠檬 9:30 就交电脑睡了），可是万恶的 *** 以睡不着的名义把我拉过去打 UNO,
然后我只能被逼无奈地去打 UNO, 到 11:30 才睡可还行。

Day4

今天终于 A 了一题，今天终于 A 了一题，今天终于 A 了一题。
还有 % 一 % 全场 rank1 的柠檬。

第一题我手玩了一下得出了一个十分精简的结论，按照这个结论三四十行代码就能解决，
自己都不敢相信啊，今天终于有一道良心签到题了？
于是打出来后不停地调试，手造各种情况的数据都跑一遍，把之前的结论完善一些漏洞之后就交了，
交了之后还是有点慌，生怕哪里出锅。
最后还是成功 AC （四天来唯一一次）。

第二题刚开始看题还觉得可做，感觉像扫描线加线段树那种，
但是看到可能有一面墙回塌后就不这么觉得了。
而且我还看错了样例，这直接导致我误解题意，本来是先选点再有墙塌（考虑方案的时候不知道哪个墙会塌），
我看样例这样跑出来不对（其实是我手玩玩错了），就以为是先塌墙再选点（提前知道哪面墙会塌后考虑方案），
于是 blablabla 后交上去，预计至少有个二三十来分，结果只有大暴力 3' （还好大暴力的数据没卡掉我）。

第三题就感觉完全不可做了，最后暴力都没打， 0' 。
下午讲题的时候才发现这题 25' 的部分分贼容易，就是个排序加贪心。
另外 75' 正解好像是用 dp 做前面 25' 在对后面 75' 的求和用 dp 套 dp, 好巧啊之前朱哥才讲过。

A 了一题心里比较舒服，于是下午就颓了好久，打 Nazo 自力更生到 level 8 就不会了，
在网上找提示后玩到 level 11 后再次卡关。

另外碰到一件玄学的事，我那显示器一碰就断电，然后要不断地调那根线，
直到调到某个位置才可以打开，大概是因为接触不良，
然后一次又黑了，我调了贼久试遍了各种姿势还是然并卵，
没法子了，去找老师实在不行换个位置，
老师了解状况后过来随手一拨，真的是 随手一拨 ，那显示屏就开了，就开了，开了，了，
emm 不愧是金牌教练，真的 6 。

晚上本来去吃必胜客的，但是没注意到今天周日，人巨多，排队等座位都要半个小时，
几经周折最后去了 KFC ，也还不错。
旁边一家奶茶店搞活动，把一个计时器按到刚好 10s 就能领两大杯奶茶，然而大概是我脸黑，按了 3 次都差的蛮远。 晚上又是 UNO, 和 tyr 无意间相互精准放炮，
连续两次 tyr （下家）只剩一张牌，我掐指一算，猜到了那张牌的颜色，
自信地打出一张其它颜色牌，结果和他数字相同。。。

NEXT

Day5 to Day8