-2147483648 Impel Down
蒙奇·D·路飞来到海底监狱Impel Down营救他的哥哥波特卡斯·D·艾斯n+1层的海底监狱有n个电梯，每个电梯连接着上下两层不幸的是，这些电梯是“薛定谔”的，即：当你到达其中一端前，该电梯的位置与运动方向均随机现已知每个电梯从一层到下一层所需的时间t[i]求路飞从顶层到达底层的期望时间
\(\\\)
由于电梯“薛定谔”的性质，可知从一端到另一端的时间期望为\(2t_i\)
由期望的线性性得，\(Ans=2\sum_{i=1}^n t_i\)
-262144 Random
时任海军大将一笑正在德雷斯罗萨的赌场中玩转盘转盘共有n个区域，编号为1~n每转一次钢珠都会随机地进入其中的一个区域求使钢珠进入所有区域至少一次所需转转盘的期望次数为避免精度误差，结果对998244353取模(n<=1e6)
\(\\\)
设\(F[k]\)为转到\(k\)个区域后还需要转的期望次数
则有\(F[n]=0,F[k]=\frac{k}{n}F[k]+\frac{n-k}{n}F[k+1]+1\)
\(F[0]\)为所求
-65536 Keys
Impel Down被攻破了n把相同的钥匙存放在n个相同的箱子中，有m名戴着相同手铐的囚犯去取钥匙这些囚犯打开一次箱子拿到钥匙就会带着钥匙跑路，留下空的箱子，否则就会回到狱中怀疑人生求跑路囚犯人数的期望为了避免精度误差，结果对998244353取模(n,m<=1e6)
\(\\\)
设\(F[i]\)表示第\(i\)个囚犯取完之后，期望跑路的人数
则有\(F[1]=1,F[i]=F[i-1]+\frac{n-F[i-1]}{n}\)
\(F[m]\)为所求
-248 Losing Weight
乌索普被七武海巴索罗米·熊拍到了一个充满食物的岛上他吃得太多了，现在的体重是m现在他要成为食物了乌索普要逃离这里，而现在ta面前有n个食人植物这些植物会捕食体重不低于正整数v[i]的食物他每天会随机遇到n个食人植物中的一个若他会被面前的植物捕食，则他会花一天的时间使自己的体重降为 max(0,m-v[i])，否则他可以花一天时间逃脱求他逃脱的期望天数(0<=n,m,v[i]<=2000)
\(\\\)
设\(F[k]\)表示体重为\(k\)时逃脱的期望天数
则有\(F[k]=\frac{1}{n}\sum_{i=1}^n[v_i \leq k](F[\max(0,k-v_i)]+1)+[v_i>k]\)
\(F[m]\)为所求
0 Mirrors
乔巴来到了布蕾的镜中迷宫这个镜中迷宫是一个有n个节点的树，乔巴位于节点1对于每个节点v都有三种情况：被布蕾抓住并送去BIG MOM的奇珍异兽收藏、逃出迷宫、等概率地通过镜子跑向相邻的空间，概率分别为c[v]、e[v]、1-c[v]-e[v]求乔巴逃出镜中世界所需经过镜子数量的期望若乔巴一定被布蕾抓走，输出-1(n<=1e5;0<=c[v],e[v]<=1;c[v]+e[v]<=1)
\(\\\)
设\(E[v]\)为乔巴走到节点\(v\)时逃离镜中迷宫所需的步数
易得\(E[v]=\frac{1-c[v]-e[v]}{deg[v]}\sum_{u} (E[u]+1)+e[v]E[v]\)
对于叶子节点，有：\(E[v]=(1-c[v]-e[v])(E[f[v]]+1)+e[v]E[v]\)
这样从叶子节点往上推，不断消元消掉\(E[u](u \in sn[v])\)的项，能保证除根节点外每个节点的期望可用形如\(aE[v]+bE[f[v]]+c=0\)的方程表示
推到根节点时，由于\(E[1]=\frac{1-k[1]-e[1]}{deg[1]} \sum_{u \in sn[1]} (E[u]+1)+e[1]E[1]\)中，不存在\(E[f[1]]\)项
可得形如\(aE[1]+c=0\)的一元一次方程
\(c=0\)时答案为\(0\)
否则\(a \to 0\)时无解
否则\(E[1]=-\frac{c}{a}\)为所求
512 Cake
BIG MOM的午餐全是甜点她吃到k个蛋糕时再用1个单位时间有p[k]的概率吃蛋糕或者休息她想知道自己吃n个蛋糕所需时间的期望(0<=p[k]<=1;n<=1e4)
\(\\\)
设\(F[k]\)为吃完\(k\)个蛋糕后还需时间的期望
则有\(F[n]=0,F[k]=p[k]F[k+1]+(1-p[k])F[k]+1\)
\(F[0]\)为所求
2048
德雷斯罗萨的战场上“力库王殿下，老夫这次和你押的是同一边。”一笑掷了三个骰子，这三个骰子分别有k1,k2,k3(1<=k[i]<=6)面，每次某个面朝下的概率相等给定三个正整数a1,a2,a3(a[i]<=k[i])计数器的运算法则：sum=(k1==a1&&k2==a2&&k3==a3)?0:sum+k1+k2+k3;再给定一个正整数n问使得sum>=n投掷次数的期望(n<=300)
\(\\\)
设\(F[i]\)为当前计数器为\(i\)时到达目标状态的期望投掷次数
设\(p[v](3 \leq v \leq \sum_{i=1}^3 k[i])\)为投出总和为\(v\)且不使\(sum\)清零的概率(暴力枚举即可)
则有\(F[v]=0(n \leq v),F[v]=(\sum_{i=3}^{\sum_{j=1}^3 k[j]}p[i]F[v+i])+(F[0]\prod_{i=1}^3 \frac{1}{k[i]})+1\)
高斯消元解方程组即可
\(F[0]\)为所求
\(TO \ BE \ CONTINUED\)