KeBlog

先喷一句，没有大样例，差评。
再喷一句，数据水，好评。

预计 80' ，实际 110' 。

我真是个奇葩实际分比预计分高。。。

Day0-

省选前三天教练每天给我们推一道题，都是主席树应用（教练曰“线段树模板”）。
都是看了题解的思路才做出来的，自己想就找不到用主席树维护的地方。

不知道为什么这三天效率都挺高，这三天我 A 的题目估计有我平常一个星期的 A 题数。。。

然而还没来得及复习每个知识点，省选就来了。

Day1

预计 70' ，实际 40' 。

fish

我看到这题的时候就意识到我只能打暴力了。
计算几何？我对这块一片空白。
好吧，硬要说思路我大概想得到枚举线段，按斜率搞个什么数据结构？
然后真的不会，敲暴力滚粗。

预计 20' ，实际 20' 。

jojo

前缀和后缀相同？求 KMP 的 fail 数组嘛。
暴力求，一次加几个字符就求几次 fail, 全加起来就是答案。
可持久化？版本树像个 AC 自动机，但是没管这么多，无脑写了个可持久化数组。
因为是把每个字符暴力求的，只能过前 50' 。 结果我后面 30' tm TLE 了？ $ O(n log(n)) $ 的时空复杂度跑 1e5 要 6 秒？

预计 50' ，实际 20' 。

polygon

什么鬼畜题啊，简化一波题意。
把线段看做一个区间，除 (x, x + 1) 外每个区间一定可以划分成两个子区间。
然后把每个区间看做一个点，相当于有了一个满二叉树。
然后旋转操作就相当于把一个点 blablabla 换一下位置。
旋转次数可以贪心，方案数不会，大概要 DP ？
然后想着就求旋转次数吧，看看数据范围。。。
沃日 90% 的数据都要求方案数？小 W 的心情得多差啊。。。
当时我还没打其他题，感觉比较亏，就先做前面的题了，结果最后都没打。

预计 0' ，实际 0' 。

Watering

下午直接去机房颓废，死神 vs 火影真好玩。
还有被 lyy 安利太阳系争夺战，画风清新，内容硬核。

Day2

emm, 我是来测数据湿度的。。。
结果真被我水过去了。。。

预计 10' ，实际 70' 。

所以说有想法就要实现 不然就没事干了 2333 。

tour

u = v 或者 s[u] = s[v] 且 u, v 相邻的时候 (u, v) 一定是可行的。
其他点对 (u, v) 可行当且仅当 s[u] = s[v] 且存在 u -> u2, v -> v2 且 (u2, v2) 可行。
DP ？有环。
然后就只能把一个点对看做一个点，对于新的点建图，如果从初始的可行点能跑到 (u, v) 则 (u, v) 可行。
点数 $ O(n^2) $ ，边数 $ O(m^2) $ ，复杂度 $ O(n^2 + m^2 + q) $ 。
然而第一档暴力 m 就有 1e4 ， 纯随机数据开O2 本地测了一下跑 5s, 真棒。

预计 0' ，实际 30' 。

dance

好迷啊，看了看 n = 1 有 40' ，就去想 n = 1 怎么做，
推了推就是个式子： $ ans_i = _{j=0} C_L^{i+j k} W^{i+j k} $ 。 把每个 $ C_L^x W^x $ 算一遍，快速幂复杂度 $ O(L log(L)) $ ，
然而 L 有 1e8 。。。
线性都跑不过去吧这，但我实在没别的思路，就想试试线性。
做法就是预处理，预处理 L 以内的逆元和 $ W_i $ ，再线性求一排的组合数。
时空复杂度都是 $ O(L) $ ， 开 O2 本地测试 17s, 就算不 TLE 都得 MLE 。

预计 0' ，实际 30' （考完后再放本地测可以水 40' woc）。

看了看实际的 L 只有 1e7 到 2e7 左右，真棒。 至于空间，我还算有点脑子搞了波动态开空间，不然直接开 1e8 的数组肯定得炸。

sequence

b 是整数的话还能枚举枚举。分数？没救了感觉。
于是只打了 10' 的整数 DP 。

预计 10' ，实际 10' 。

Watering

下午本来打算去黄兴街打游戏的，先去麦克唐纳德吃中饭，吃完后发现就已经 3 点多了没什么时间。
于是放弃了 xbox 又回到机房颓废，死神 vs 火影昨天已经玩熟练了，打起来比较轻松。

Day3+

省选完了，结果并不想想象的那样，即使运气眷顾了我还是 wei 的一批。
实力不够啊，说啥都是扯淡。

常规欠下的帐也该还了，滚回去学文化课啦，接受作业的洗礼。

One Year Later

update on 2020.04.08

一年过去了，重新审视了去年的 HNOI ，再次分别总结一下吧。 （从去年省选到现在，这些题碰都没有碰过）

新一轮省选不远了。

fish

咕咕咕。

jojo

去年，我甚至不知道均摊数据结构是不能可持久化的，打了一个主席树满以为复杂度一个 log 。
可事实上 KMP 的最坏复杂度是 \(O(n)\) ，可持久化后复杂度可以到 \(O(n^2)\) 。

可是现在我还是不会做 jojo ，甚至看题解也看不懂，现在上考场估计也还是 20pts 。

polygon

这题不难的啊，至少现在我看来如此。
不考虑修改的话就可以分治处理这个问题，考虑上修改就动态维护分治的树状形态即可。
而方案数就是分治树的拓扑序数量。

A 了，现在上考场有信心拿到 100pts ，只不过可能得花上至少 2h 的时间。

tour

思路很妙，同类型的边的偶环是没有意义的，可以删边使得同类型的边偶环不存在进而把边数控制在 \(O(n)\) 。
可惜我没能独自得到这个结论，还是看了题解的，看了后有一种恍然大悟的感觉。

现在上考场也许还是只会 \(O(m^2)\) 暴力吧，时间足够的话说不定能想到正解，但没有把握，大概拿 30pts 。

dance

现在看来这个式子并不难推，推完后就是对一个多项式求单位根上的点值。
但是在直到看题解前我都完全没听说过 bluestein ，算是技不如人，只能拿 60pts 。

sequence

花了 30min 打了个 50pts 的暴力 \(O(nm)\) ，发现简直白给。
不过 100pts 确实难了不少，我觉得就算考场想到了也无法在考试时间内写对。

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

静态页面博客

这个用 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 满足：
对任意 $ 0 k P - 2 $ ， $ g^k $ 互不相同。 有些模数可能不存在原根，这里先假设模数都有原根。

假设系数是模 P 意义下的，P 是形如 $ 2^k + 1 $ 的质数，其原根为 g ，
设 $ G_n = g^{} mod P $ ，其中 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_1X + a_2X^2 + ... + a_nX^n $ 的代数表达式叫做多项式， 可以记作 $ P(X) = a_0 + a_1X + a_2X^2 + ... + a_nX^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(n log_2n) $ 的 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^2a \equiv 0 (mod \; x^n) \;\;\;\;\; (6)\] 移项，整理： \[ b = (2c - c^2a) \; mod \; x^n \]

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

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

其中乘法使用 FFT ，则最终时间复杂度为 $ O(n log_2n) $ 。