UOJ #299

题意

小 R 和小 B 玩了 $n$ 局游戏，第一局小 R 获胜的概率是 $p_1$，对于第 $i(1<i\le n)$ 局，若第 $i-1$ 局小 R 获胜，则小 R 获胜的概率为 $p_i$，否则为 $q_i$

现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 $m$ 次增加或删除已知条件后都输出答案

$n,m\le 2\times 10^5$

后面的游戏结果会影响前面的概率 = =

UOJ #345. 【清华集训2017】榕树之心

题目背景

深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。

……

LOJ #2014. 「SCOI2016」萌萌哒

题意

有一个没有前导零的 $n$ 位十进制数 $S_1 S_2\dotsc S_n$，$m$ 条限制，一条限制形如 $S_{l_1}S_{l_1+1}\dotsc S_{r_2}$ 与 $S_{l_2}S_{l_2+1}\dotsc S_{r_2}$ 这两个子串需要完全相同

问有多少种合法的方案

模 $10^9+7$

AGC005E - Sugigma: The Showdown

题意

有 $n$ 个点，$n-1$ 条红边和 $n-1$ 条蓝边分别把这些点连成一棵树

一开始第一个人在 $x$，第二个人在 $y$，第一个人先手，轮流操作

第一个人走红边，第二个人走蓝边，每次操作可以不动或走一条边。

当两个人相遇的时候游戏结束，第一个人希望最大化总步数，第二个人希望最小化，两个人绝顶聪明

问游戏能否结束，如果可以结束输出最后的步数

Codeforces 755G. PolandBall and Many Other Balls

题意

有 $n$ 个球编号为 $1,2,\dotsc,n$，一组可以是一个球 ${i}$ 或者是两个相邻的球 ${i,i+1}$

对于 $i=1,2,\dotsc,k$ 求 $n$ 个球划分成 $i$ 组的方案数，每个球至多在一个组内，并且可以不在任何一个组内

对 $998244353$ 取模

$n\le 10^9,k\le 2^{15}$

LOJ #2983. 「WC2019」数树

题意

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在边 $(p, q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。

• 问题 1：已知第一棵树，对于第二棵树的所有 $n^{n−2}$ 种选择方案，求问题 0 的答案之和。

• 问题 2：对于第一棵树的所有 $n^{n−2}$ 种选择方案，求问题 1 的答案之和。

对 $998244353$ 取模

BZOJ 3684: 大朋友和多叉树

题意

求包含 $s$ 个叶子，非叶子节点的孩子数目在集合 $D$ 中的有根树数量。

孩子之间有顺序，保证 $1\notin D$。

模质数 $950009857=453\times 2^{21}+1$

$s,|D|\le 10^5$

LOJ #6391. 「THUPC2018」淘米神的树 / Tommy

题意

有一棵 $n$ 个点的树，你要以一个顺序选择每个点恰好一次。

初始只有两个钦定点 $a,b$ 可以被选，一个点被选后所有的相邻点就可以被选择。

求方案数，模 $998244353$

Codeforces 1097G. Vladislav and a Great Legend

当时不会做

题意

给定一棵 $n$ 个点的树

对于每个非空的点集 $X\subseteq {1,2,\dotsc,n}$，定义 $f(X)$ 表示最少的能让点集 $X$ 联通的边的数量

求

$$
\sum_{X\subseteq {1,2,\dotsc,n},X\ne \varnothing} (f(X))^k
$$

模 $10^9+7$

$n\le 10^5,k\le 200$

UOJ #269

题意

给定 $m$ 次函数 $f$ 和 $n,a$，求

$$
\sum_{k = 0}^{n}f(k)\binom{n}{k}a^k(1 - a) ^{n - k}
$$

模 $998244353$

函数给出 $0,1,\dotsc,m$ 处的点值

$1\le n\le 10^9,1\le m\le 2\times 10^4$