A

考虑用容斥解决问题。

排列数：$n!n!$

没有位置 $p_i≠ip\_i\; \backslash not\; =\; i$ 的排列数：$11$

恰好 2 位置 $p_i≠ip\_i\; \backslash not\; =\; i$ 的排列数：$\left(\genfrac{}{}{0px}{}{n}{2}\right)\backslash binom\{n\}\{2\}$

恰好 3 位置 $p_i≠ip\_i\; \backslash not\; =\; i$ 的排列数：$2\left(\genfrac{}{}{0px}{}{n}{3}\right)2\backslash binom\{n\}\{3\}$

那么可以得到答案为 $n!-1-\left(\genfrac{}{}{0px}{}{n}{2}\right)-2\left(\genfrac{}{}{0px}{}{n}{3}\right)n!-1-\backslash binom\{n\}\{2\}-2\backslash binom\{n\}\{3\}$。

B

结论：David 必胜。

证明：考虑归谬法。不妨假定 Adam 必胜，设 David 第一步选点 1 的时候 Adam 会选择点 $xx$。那么 David 第一步直接选 $xx$ 即可获胜，所以假设不成立。

C

sol1

设精度限制 $ϵ=10^{-9}\backslash epsilon=10^\{-9\}$。

性质：最优的圆必然和一条边相切。如果不然，则由于所有点共线，可以向垂直于线的方向“挤”圆，使其贴到边上。

所以直接二分半径，对于一条边，每个点对应着一段开区间，代表切点不可能在这段区间内。对所有区间取并看有没有剩余的即可。注意要把两边的限制也判断进去。

几个优化：

1. 由于当点的 $xx$ 坐标有序时，所有的区间的中点递增，所以可以不用每次二分判定的时候排序，可以少一个 log。
2. 另一个性质是，圆的半径至少是 $\min (n,m)\mathrm{/}4\backslash min(n,m)/4$，因为将长方形横着切一刀，竖着切一刀分成四块，一条直线最多经过三块，另一块的最大圆就是下限。所以直接二分 $\log {ϵ}^{-1}\backslash log\; \backslash epsilon^\{-1\}$ 轮即可将相对误差减小到 $o(ϵ)o(\backslash epsilon)$。

优化完后的复杂度为 $\mathcal{O}(k\log {ϵ}^{-1})\backslash mathcal\{O\}\backslash left(k\backslash log\backslash epsilon^\{-1\}\backslash right)$，不加优化也能过，但是会被卡精度，要开 long double，失策了，谢罪。

sol2

考虑分类讨论限制圆范围的因素。

• 圆被对边限制

核心即为判断 $\min (n,m)\mathrm{/}2\backslash min(n,m)/2$ 的半径能否存在，显然圆心只有可能在一条线段上。

每个点对应一段区间，使得圆心不能在区间内。求区间并判一下即可。

• 圆被两条邻边和一个点限制

对于一个角，对所有点计算以这个点为限制时的半径，取最小值即可。

• 圆被两个点和一条边限制

注意到每个点的限制是一条抛物线，考虑将两条抛物线求交以后判断。

先特判掉 $y_1=y_{2}y\_1=y\_2$ 的情况（否则后面可能不是二次方程）以及 $y=0y=0$ 的情况（注意到这不优于第二类限制），然后就可以直接将两条抛物线的解析式求出来，作差以后用二次方程暴力解横坐标。也可以手推抛物线交点的式子，过程略，最后的结果是，对于两个点 $(x_1,y_1)(x\_1,y\_1)$ 和 $(x_2,y_2)(x\_2,y\_2)$，满足限制的圆交点的横坐标为：

对于每个可能的横坐标，用对应的解析式求出纵坐标（即半径）后再根据边的条件判断是否合法即可。

复杂度 $\mathcal{O}(k)\backslash mathcal\{O\}(k)$。

D

令硬币的正面为1，反面为 -1，游戏结束等价于前缀和序列的极差 $=n=n$。

设 $f(i,j)f(i,j)$ 表示极差为 $ii$，目前前缀和比历史最小值大 $jj$ 时接下来 Rikka 的胜率，容易得到边界条件 $f(n,0)=0,f(n,n)=1f(n,0)=0,f(n,n)=1$。

发现递推式子形式十分简单，直接展开即可。令 $k=\frac{1-p}{p}k=\backslash frac\{1-p\}\{p\}$，则答案为 $\frac{n}{k^n-1}-\frac{n+1}{k^{n+1}-1}\backslash frac\{n\}\{k^n-1\}-\backslash frac\{n+1\}\{k^\{n+1\}-1\}$。（注意特判 $p=\frac{1}{2}p=\backslash frac\{1\}\{2\}$）

具体的，我们定义一个数列 $A_1,A_2,\cdots ,A_{m}A\_1,A\_2,\backslash cdots,A\_m$ 是好的当且仅当对于 $i\in [2,m-1]i\backslash in[2,m-1]$ 有 $A_i=p{A}_{i+1}+(1-p)A_{i-1}A\_i=pA\_\{i+1\}+(1-p)A\_\{i-1\}$。

容易发现下列数列是好的：

• $f(i+1,0),f(i,0),f(i,1),\cdots ,f(i,i-1),f(i,i),f(i+1,i+1)f(i+1,0),f(i,0),f(i,1),\backslash cdots,f(i,i-1),f(i,i),f(i+1,i+1)$

令 $k=\frac{1-p}{p}k=\backslash frac\{1-p\}\{p\}$ ，可以发现对于好的数列有 $A_{i+1}-A_i=k(A_i-A_{i-1})A\_\{i+1\}-A\_\{i\}=k(A\_i-A\_\{i-1\})$。

令 $F_i=f(i,i)-f(i,0)F\_i=f(i,i)-f(i,0)$，有 $F_i=F_{i+1}\times {\displaystyle \frac{{\sum }_{j=1}^i{k}^j}{{\sum }_{j=0}^{i+1}{k}^j}}F\_i=F\_\{i+1\}\backslash times\; \backslash dfrac\{\backslash sum\_\{j=1\}^\{i\}k^j\}\{\backslash sum\_\{j=0\}^\{i+1\}k^j\}$

$=F_{i+1}\times {\displaystyle \frac{k(1-k^i)}{1-k^{i+2}}}=F\_\{i+1\}\backslash times\backslash dfrac\{k(1-k^i)\}\{1-k^\{i+2\}\}$

$={\displaystyle \frac{1}{(1-k^{n+1})(1-k^n)}}\times k^{n-i}(1-k^{i+1})(1-k^i)=\backslash dfrac\{1\}\{(1-k^\{n+1\})(1-k^n)\}\backslash times\; k^\{n-i\}(1-k^\{i+1\})(1-k^i)$

而 $f(i,0)-f(i+1,0)=\frac{1}{{\sum }_{j=1}^i{k}^j}\ast F_i={\displaystyle \frac{1-k}{(1-k^{n+1})(1-k^n)}}\ast (k^{n-i-1}-k^n)f(i,0)-f(i+1,0)=\backslash frac\{1\}\{\backslash sum\_\{j=1\}^\{i\}k^j\}\; *\; F\_i=\backslash dfrac\{1-k\}\{(1-k^\{n+1\})(1-k^n)\}\; *\; (k^\{n-i-1\}-k^n)$

$f(0,0)={\sum }_{i=0}^{n-1}(f(i,0)-f(i+1,0))={\displaystyle \frac{(1-k^n)-n(1-k)k^n}{(1-k^{n+1})(1-k^n)}}={\displaystyle \frac{n}{k^n-1}}-{\displaystyle \frac{n+1}{k^{n+1}-1}}f(0,0)=\backslash sum\_\{i=0\}^\{n-1\}(f(i,0)-f(i+1,0))=\backslash dfrac\{(1-k^n)-n(1-k)k^n\}\{(1-k^\{n+1\})(1-k^n)\}=\backslash dfrac\{n\}\{k^n-1\}-\backslash dfrac\{n+1\}\{k^\{n+1\}-1\}$

E

令 $f_{S,i}f\_\{S,i\}$ 表示已经选了 $ii$ 个集合，还要选集合 S 的贡献之和。初始值是 $f_{S,0}=b_{S}f\_\{S,0\}=b\_S$，答案即为 $f_{\mathrm{\varnothing },i}f\_\{\backslash empty,i\}$。

依次从状态的点集合中剔除点 $0,1,\mathrm{.}\mathrm{.}\mathrm{.},n-10,1,...,n-1$，转移可以通过 FWT 优化，时间复杂度为 $\sum i^2(n-i)2^i=O(n^2{2}^n)\backslash sum\; i^2(n-i)2^i=O(n^22^n)$，可以通过。

F

比较套路的题。这式子是超几何函数，微分有限，所以 $f(0),f(1),\cdots ,f(n)f(0),f(1),\backslash cdots,f(n)$ 可以写成整式递推的形式，暴力找出递推式后直接递推即可，时间复杂度 $O(n)O(n)$。