斯特林数
因为被一道毒瘤斯特林数题目卡掉，写一写斯特林数。
因为被一道毒瘤斯特林数题目卡掉，写一写斯特林数。
这是本博客中第一篇有关计算几何的文章，简介扫描线算法。
一种神奇的分治思想，可以顶替高级数据结构，不过需要离线。
OpenGL入门，本文以这篇文章的入门部分为基础完成。有扩展。
难度：NOI/NOI+/CTSC
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。
幻想乡一共有n个地方，那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的，一共有m条边。现在这m条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第i条边所需要的时间为ei。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。
现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那n-1条边，同时开始修复，那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of n n distinct positive integers: $c_{1},c_{2},…,c_{n}$. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$ , the weight of v v is in the set $\{c_{1},c_{2},…,c_{n}\}$ c. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices’ weights.
Given an integer $m$ , can you for all $s (1\leq s\leq m)$calculate the number of good vertex-weighted rooted binary trees with weight $s$? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo $998244353 $( $7×17×2^{23}+1$, a prime number).
难度：NOI/NOI+/CTSC
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.
刚才说过, 阿狸的国家有 n 个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通.
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.
好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出 n 个点的简单 (无重边无自环) 无向连通图数目.
由于这个数字可能非常大, 你只需要输出方案数 mod 1004535809(479 * 2 ^ 21 + 1)即可.
补充上回文自动机的文章，这是解决回文子串问题的利器。
收集一些SAM相关题目，关于SAM见这篇博客。
String matching, a common problem in DNA sequence analysis and text editing, is to find the occurrences of one certain string (called pattern) in a larger string (called text). In some cases, the pattern is not required to be exactly in the text, and minor differences are acceptable (due to possible typing mistakes). When given a pattern string and a text string, we say pattern P is approximately matched within text S, if there is a substring of S which is at most one letter different from P. Note that the length of this substring and the pattern must be identical. For example, pattern “abb” is approximately matched in text “babc” but not matched in “bbac”.
It is easy to check if a pattern is approximately matched in a text. So your task is to count the number of all text strings of length m in which the given pattern can be approximately matched, and both of the patterns and texts are binary strings in order not to handle big integers.