[LnOI2019]长脖子鹿省选模拟赛 题解

### T1 [LnOI2019SP]快速多项式变换 这是一道签到题。想必各位dalao都AC了吧。 对于100%的数据，将m带入此多项式， $$f(m)=a_0+a_1m+a_2m^2+a_3m^3+ \cdots +a_nm^n$$ 不难发现，设$a_na_{n-1}\cdots a_2a_1a_0$是一个$m$进制数，将此数转换为10进制即为$f(m)$的值。因此只需要倒序输出$f(m)$在$m$进制下每一位的值即可。 总复杂度$O(logn)$ 题解By 朝田诗乃 ### T2 [LnOI2019]加特林轮盘赌 说这个题目的$n$是$10^4$，当$n=0$和$n=1$的时候答案是显然的,然后我们考虑两个人的情况。比方说两个参赛者，一个yyy，一个雪碧。先崩yyy，如果他$P_0$的概率崩死了，那yyy没了，剩一个雪碧，雪碧赢了；如果他$(1-P_0)$的概率没死，那么游戏要继续呀。雪碧来到了第一位，yyy相当于到了第二位。其实这个局面，和开枪前没有区别，只不过是yyy和雪碧互换了位置罢了。 *//以上题解由$X$口述，朝田诗乃记录。* 这样，我们设$F[2][1]$表示第一个人**最终幸存**的概率，$F[2][2]$表示第二个人**最终幸存**的概率。 $$ F[2][1] = P_0 * 0 + (1-P_0) * F[2][2] $$ 作为一个二元一次方程，我们还需要一个等式才能解出他们，不难想到： $$ F[2][1] + F[2][2] = 1 $$ K个人呢？头两个式子我们可以抄上面的啊！ $$ F[n][1] = (1-P_0) * F[n][n] $$ $$ F[n][1] + F[n][2] + ... F[n][n] = 1 $$ 当前我们在崩第1个玩家，这个时候排在第k位玩家的概率会是怎么样的呢? 概率$1-P_0$：如果第一个玩家没被崩死，所有人都向前走了一步！ $$F[n][k] -> F[n][k-1]$$ 概率$P_0$：如果第一个玩家被崩死，所有人还是都向前走了一步！ $$F[n][k] -> F[n-1][k-1]$$ 不过因为死了一个，所以总人数也少了一个。 故： $$ F[n][k] = P_0 * F[n][k-1] + (1-P_0) * F[n-1][k-1] $$ 这一共能给你$n$个等式。 由于最后有且仅有最后一个幸存者，所以有 $$\Sigma_{k=1}^{n}F[n][k] = 1$$ 解n元一次方程，高斯消元能拿10pts。 手动消元就能100pts了。 最后要特判一下$P_0=0$的情况。 总复杂度$O(n^2)$ 题解By X *//朝田诗乃：居然被那么多人水过了QAQ* ### T3 [LnOI2019]东京夏日相会 ~~这题可能是全比赛最水的一题，果然诗乃还是比较菜~~ 考虑将圆拆成点。我们在圆上均匀取点。设此时处理的圆半径为$r$，每隔$d$度圆心角取一个点。可以证明当 $d ≤ acos(1-0.005/r)$ 时所得的答案与标准答案差距不超过$0.01$.证明是初中基础数学请各位自己推一下。 剩下就是解决最小圆覆盖点的问题了。请移步[P1742](https://www.luogu.org/problemnew/show/P1742)。 总复杂度期望$O(n)$ 随机/退火本来想卡一下的，但后来还是放宽了精度限制QAQ 题解By 朝田诗乃 ### T4 [LnOI2019]第二代图灵机 对于20%的数据，对于每个Q操作，用$O(n)$的复杂度在$[l,r]$之间进行尺取（若熟悉尺取法可跳过）： 对于3操作， **定理1** :若一个合法区间$[l_1,r_1]$被另一个合法区间$[l_2,r_2]$包含，则$[l_2,r_2]$一定不是最优解。 由于数字都是正整数，证明显然。 **定理2** :若一个区间$[l_1,r_1]$是合法区间且$[l_1,r_1]$内不包含其他合法区间，则$[l_1+1,r_2](l_1+1 ≤ r_2 ≤ r_1)$一定不是一个合法区间。 ~~这好像是废话~~ 因此我们可以枚举左端点和与其对应的最优右端点，记为$f(l)$，则$f(l)$单增，枚举复杂度$O(n)$。 对于4操作，尺取，过程与3几乎没有任何区别这里不在赘述。 对于100%的数据： 使用珂朵莉树(ODT，又称老司机树)维护颜色序列，由于数据随机，可将所求区间$(l,r)$中的节点个数降到$log$级别（证明百度，我也不记得为什么了），同20%做法进行暴力尺取。使用线段树维护区间数字和以更新答案。特别的，对于4操作，直接尺取可能丢失某些情况，因此我们还需要维护区间数字最大值。（这个实现的时候就会知道了） 在随机数据情况下，总复杂度$O(nlog^2n)$ 题解By 朝田诗乃 数据与标程下载：[点这里](https://pan.baidu.com/s/1Kbupn_jT0z_eKXzUabcutw) 提取码：f2c4 hanabi0和hanabi8是错误数据，忘记更新包了，实际测试时用hanabi1和hanabi9分别替代了，大家当没看见就好惹