LuoguLOJ分析设 $P=\sum_{i=1}^n p_i$。设 $F(x)$ 为按到目标状态的指数型概率生成函数,$G(x)$ 为按回自己的指数型概率生成函数。$F(x)$ 直接把每个开关乘在一起即可,$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有直接计算即可。代码// ==================================== // author...
LuoguLOJ分析我们画出每条路线的 $t-E$ 图像,大概是这个样子的(蓝色的是原函数,红色的是它的导数):感性理解一下可以知道,最后每条路径在其消耗的能量处的导数相同。于是我们可以二分这个导数,然后把每段的速度求出来,算一下总能量是否 $\leq E_U$ 来 check。现在考虑已知导数怎么算速度。我们有这个东西在 $[v',+\infty)$ 上是单增的,所以同样可以二分出 $v$...
LuoguLOJgjh 与地下城分析一种 FFT 做法考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。可以发现转移是一个多项式快速幂,于是直接 FFT 就可以了。(大概)可以理解成概率生成函数卷积?然而 FFT 掉精度很严重,我只能过 $60$ 分。所以对于大数据要考虑其它做法。一种定积分做法首先要知道中心极限定理的一个推论:设有 $n$ 个独立同分布的随...
权限题嘤嘤嘤分析设$f(x)$为直线$x$与所有圆的交的并的长度(好绕)然后就是自适应辛普森法的板子。然后数据卡我精度,打了表才过qwq代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #i...