CSP-S 前要多做树上问题 （主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题，然后爆炸了） 。

这题一看就是树形DP，状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数，枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$。

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌，第 $i$ 首歌播放时间为 $t_i$ 秒，且每播放一秒都会有 $p_i$ 的概率被识别出来，跳到下一首。某首歌播放时间过完默认被识别，也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望，不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒，注意一下边界即可。

为了准备初赛，发现自己对P问题、NP问题和NPC问题一点都不熟悉，在网上找到了 Matrix67 大佬的博文，感觉很棒，所以转载一下。

其实是太久没写博文了来充数的

原文链接

遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

以下为原文，对公式略加修改，删改了逻辑电路部分内容，并且重绘了逻辑电路图（原文排版实在难以看清）。

作为一道英文题，我们先解释一下题意。

题面有点长就不解释了，大家自己翻译吧。

首先有一个 Simple 的想法，直接维护啊，变的节点又不多，修改不是 $O(1)$ 的吗？

然后发现错了。

接上文 https://sxyugao.top/p/22002c08.html

最近折腾了一下 Arch Linux，写一篇安装教程纪念一下。

环境为 HP Notebook x86_64，UEFI。

前言

作为 Windows 用户，常羡慕 Linux 用户高端大气的终端。

其实，Windows 自带的 PowerShell 也十分的强大。

但是过于简陋的界面不知道劝退了多少用户，于是让我们来美化一下 PowerShell 吧。

以下教程环境均为 PowerShell 5.x。

首先我们要知道这道题的原型是「NOI2014」起床困难综合症。

总是有出题人喜欢把序列上用线段树解决的题目出到树上，让选手强行写个树链剖分或树分治或某种动态树数据结构。

序列问题转化为树上问题，很容易想到树链剖分，直接上板子。

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$，于是根据取模的性质把原式两边同乘九再加一，原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$。

可以发现这是个 BSGS 的标准式子，由于 $m$ 保证为质数，所以也不必用拓展 BSGS。

作为一道英文题，我们先解释一下题意：

给你一棵树和它的一个 BFS 序，让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时，大部分人都会想到，既然是树，那么它一定是一层一层地向下 BFS。

也就是说，BFS 序中越后出现的节点，它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后，发现 Wrong Answer 了。