「UOJ 299」「CTSC2017」游戏
题意
小 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\)
后面的游戏结果会影响前面的概率 = =
小 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\)
后面的游戏结果会影响前面的概率 = =
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。
……
有一个没有前导零的 \(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}\)
本题包含三个问题：
问题 0：已知两棵 \(n\) 个节点的树的形态。要给予每个节点一个 \([1, y]\) 中的整数，使得对于任意两个节点 \(p, q\)，如果存在边 \((p, q)\) 同时属于这两棵树，则 \(p, q\) 必须被给予相同的数。求给予数的方案数。
问题 1：已知第一棵树，对于第二棵树的所有 \(n^{n−2}\) 种选择方案，求问题 0 的答案之和。
问题 2：对于第一棵树的所有 \(n^{n−2}\) 种选择方案，求问题 1 的答案之和。
对 \(998244353\) 取模
求包含 \(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\)
给定 \(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\)