求有向图强连通分量的一种算法。 算法步骤： 用 dfs 遍历整个有向图，取出它的后序遍历（可能是多次dfs，但并不影响，可以直接拼起来）。 建反图（原图的每条边反向），按照后序从后往前，以它为起点遍历反图。 遍历反图时，所有能够到达的，未经过的点（一定是序列中在它之前出现的）都和起点在一个强连通分量当中。 为什么正确？对反图 $u$ 能到达 $v$…

IO 读入优化 char Getchar(){ static char now[1<<20],*S,*T; if (T==S){ T=(S=now)+fread(now,1,1<<20,stdin); if (T==S) return EOF; } return *S++; } int read(){ int x=0,f=1…

普通幂转第二类斯特林数：$i^k=\sum\limits_{j=1}^{i}S_{k,j}\times C_{i,j}\times j!$。 第二类斯特林数求自然数幂和：$\sum\limits^n_{i = 0}i ^ k = \sum \limits _ {j = 1} ^ n S_{k, j}\times j! \times C_{n + 1…

IO 读入优化 char Getchar(){ static char now[1<<20],*S,*T; if (T==S){ T=(S=now)+fread(now,1,1<<20,stdin); if (T==S) return EOF; } return *S++; } int read(){ int x=0,f=1…

Day2 T3 Thousands Islands 待填。 Catfish Farm 第 $i$ 列哪些鱼被抓住，只和第 $i$ 列堤的高度，以及 $i-1/i+1$ 列中较高堤的高度有关。 容易想到按列 dp，这样第 $i$ 列就有两种情况，较高的列是 $i-1/i+1$。 这个较高没有必要，仅仅多加了限制，所以可以每个 $i$ 自由选择 $i-…

constructive 566E 对于一对相邻的点 $(x,y)$，它们其它的相邻点之间的交集就是 ${x,y}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的（出现的点如果不相邻那么它们路径上的也应该在交集中）。 这样可以求出所有非叶子节点之间的连边，剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。 这样非叶…

Greedy 1472F 从左到右考虑每一列， 确定了前 $i-1$ 列，那么现在的第 $i$ 列哪些被覆盖就确定了。 可以求出第 $i$ 列覆盖的方案：如果没有空格/只有一个空格，则只能放横的；否则两个都是空格，一种是放两个横的，一种是放一个竖的，可以发现放两个横的和放两个竖的等价，不如变成放竖的，其它的之后再决策。 所以就变成，只要这一列没满，…

1523E 刚开始想的是直接 dp，记录当前两端都没有/左右有一盏/两端都有的答案，转移就考虑哪个范围能继续递归。 其实可以有另一种思路，期望等于 $i$ 次操作后还没结束的概率之和+1（即 $E(x)=1+\sum_{i\geq 1} P(x>i)$）。 那么每一盏灯（除了最后一盏）就要求它后面 $k-1$ 个位置都没有灯，组合数就能计算 …

是什么 Min_25 筛是一种求积性函数前缀和的算法。 具体来说，对于一个积性函数 $f$，求： $$ ans=\sum_{i=1}^n f(i) $$ 需要快速计算素数的幂的值。计算素数个数函数 $\pi(n)$ 的时间复杂度为 $O(\dfrac{n^{\frac{3}{4}}}{\log n})$（它只用到第一步），计算其它函数时间复杂度为 …

支配树 支配 称节点 $x$ 支配节点 $u$，当且仅当从起始点到 $u$ 的每一条路径都必须经过 $x$。根据定义，每个节点都支配它自身。 称节点 $x$ 严格支配节点 $u$，当且 $x$ 支配 $u$ 且 $x$ 不等于 $u$。 方便起见，只考虑从起始点开始能到达的节点。显然严格支配关系一定不存在环。 称节点 $u$ 的直接支配节点为 $x…