学了这么久的线段树，竟然从没写过树上线段树。其实本质还是线段树。只是把一开始的树结构用 dfs 序变成线段的形式，然后再用线段树加速。

好久没做 状态dp 的问题了，经常用来将 NP 问题，变得小规模可解问题。确实是一个很经典的东西，最重要的是知道 $dp[i][j]$ 的意义，其次才是状态转移。

codeforce 上有一道题 。 rng_58 用一个奇妙的公式解决了这个问题。并且给出了公式的证明，这里给出另一个比较好的证明。

之前其实写过几篇博客零散的讨论过这个问题，但是要么结论不强，要么证明不优美，这次突发奇想，一下子看穿了二阶的情形。
在之前博客中讲过
$$ |GL(n,p)| = \prod_{i=0}^{n-1} (p^n-p^i) $$
即对任意 $n$ 阶可逆矩阵 $A$， $A^{|GL(n,p)|}=I_n$。
我们通常求 $n$ 阶线性递推关系表示的数列时都是用矩阵来做的，此时的矩阵其实对应着它的有理标准型，是一类特殊的矩阵，因此很有可能，此类矩阵的周期仅仅是 $|GL(n,p)|$ 的一个因子。

在C语言中最常用的函数应该就是scanf，printf吧。对于大量输入输出时C++也常用scanf和print代替cin和cout。然而我们学习C语言最先接触的scanf和printf其实我们并不完全了解。

我们可以把计算机看成一个函数，将一份代码映成一段输出，那么输出为代码本事就是数学中不动点。任意语言都有很多相应版本的这种程序，原理都是类似的，我自己写的C++代码如下：

之前写过一篇博文：自然数方幂和公式，这次写的目的是因为上次是从数学上完美的解决了这个问题，这次我们要从计算上完美到无法诠释的解决这个问题，当然这归功于我看到的一份sgtlaugh的代码。经过解读体会到其中的奥秘，特此记录。一句话，简直不敢相信。

如果有人说他能在 $O(k)$ 时空复杂度求解 $\sum_{i=1}^n i^k$，你肯定会说这怎么可能别忽悠我了，那我只能说，因为你没看过这篇博文。

阅读全文 »

最长递增子序列最常规的做法是 $O(n^2)$ 的动态规划（dp） 做法（很容易想到不多说了）。这里可以维护一个单调的数列使其复杂度降至 $O(n \log n)$。相应的最长递减、不升、不降子序列完全类似，相应修改即可。另外，这个问题让我想起另一个降低复杂度的经典例子：连续子序列最大和。从 $O(n^3)$ 到 $O(n^2)$ 再到 $O(n)$.