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\)

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

LOJ #6509. 「雅礼集训 2018 Day7」C

题意

给定一棵 \(n\) 个点的树，树上每个点初始有一个 \(0\) 或 \(1\) 的数字。

考虑这样一个过程：

1. 等概率随机选择一个点作为起点
2. 等概率随机选择一个新点并沿着树上的路径移动过去，最后反转这个新点上的数字（注意只反转这个新点上的数字而非经过的所有点的数字）
3. 如果此时整棵树上的所有数字相同，则过程结束；否则回到步骤 \(2\)

求出期望的移动距离，对 \(10^9 + 7\) 取模。

\(n\le 10^5\)

LOJ #2145

Zeit und Raum trennen dich und mich.

时空将你我分开。

题意

你有一排\(n\)个灯泡，有初始状态\(0/1\)，从\(1\)开始编号

一次操作可以选定一个整数\(x\in[1,n]\)，把\(x\)的所有约数号（含\(1\)和\(x\)）灯泡状态取反。

你要把所有灯泡变成\(0\)，给出\(0\le k\le n\)

1. 若剩余最小操作次数\(\le k\)，你会直接按照最小操作次数操作，并结束

2. 否则每次你会在\([1,n]\)中等概率地选择一个整数进行操作，直到满足1的条件

求期望操作次数乘\(n!\)对\(100003\)取模的结果

\(1\le n\le 10^5\)