$n$ 个点，随机构成一颗有根树，求叶子的期望数量，$n\leq 10^9$.

问题 给定 $n, k$，求出： $$ 1^k+2^k+\cdots+n^k=\sum_{i=1}^{n}{i^k}\bmod 1000000007 $$ $n\leq 10^9$，$k\leq 10…

对于一个字符串 $s$，求出一个尽可能短的回文字符串 $s^{*}$，同时使得 $s$ 是 $s^{*}$ 的前缀。
$|s|\leq 10^5$.

给定无向图，每条边以 $p_i$ 的概率存在。求存在的边构成一棵生成树的概率。
点数 $2\leq N\leq 50$，无重边。

比赛链接：「Wdoi2021」Windy OI Round3

比赛链接：【LGR-088】洛谷 8 月月赛 & 「PMOI」Round · 04

有一个长度为 $n$ 的数字序列 $a$，对这个序列的任意一个连续子串，求所有数字之和，重复出现的数字只被统计一次。问第 $k$ 大的和是多少。

给定一个 $n\times m$ 的矩阵，矩阵上每一个点可能是狼、羊或者空地。
你需要在格子的边界修建篱笆，使得任意两个狼与羊的格子不连通。
给一个格子的一条边界修建篱笆，那么篱笆总长度增加 $1$，求篱笆的最短长度。
$n, m\leq 100$.