Temp

其它

---

BZOJ
UOJ

感觉网上大部分题解对我这种数学基础差的人来说十分不友好...（虽然理解后也觉得没有那么难）结合两篇写的比较好的详细写一写。如果有错要指出啊QAQ
https://blog.csdn.net/smallsxj/article/details/73205569
https://www.cnblogs.com/wujiechao/p/7781140.html

---

首先题目要求输出精确的小数，由下面的推导可知答案要么是整数，要么是一位小数$.5$，不会是$.25,\ .125$什么的。
对$k$讨论，先以$k=2$为例，假设期望异或和是$S$，把它二进制拆分，每一位记为$b_i=0/1$，那么答案是$(b_02^0+b_12^1+...+b_m2^m)(b_02^0+b_12^1+...+b_m2^m)=b_0b_02^0+b_0b_12^1+b_0b_22^2+...b_mb_m2^{m+m}$$=\sum_i\sum_jb_ib_j2^{i+j}$。
那么对于$b_i,b_j$，它的贡献是$\frac{P}{2^n}\times2^{i+j}$，$P$是$i,j$两位都为$1$的方案数。
那么用$b_{i,j}$表示第$i$个数二进制拆分后的第$j$位，$x_i$表示这个数是否存在于选出的集合中，求$i,j$位都为$1$的方案数，可以列个方程组：

$$\begin{matrix}x_1b_{1,0}\oplus x_2b_{2,0}\oplus...\oplus x_nb_{n,0}=0/1\\x_1b_{1,0}\oplus x_2b_{2,0}\oplus...\oplus x_nb_{n,0}=0/1\\\dots\\x_1b_{1,i}\oplus x_2b_{2,i}\oplus...\oplus x_nb_{n,i}=1\\\dots\\x_1b_{1,j}\oplus x_2b_{2,j}\oplus...\oplus x_nb_{n,j}=1\\\dots\\x_1b_{1,m}\oplus x_2b_{2,m}\oplus...\oplus x_nb_{n,m}=0/1\end{matrix}$$

（个人感觉这里除去$i,j$的方程的右式应该是$0/1$吧，那篇博客里写的是$0$）
解这个方程组，可以发现只会有$t\leq k$个$x_i$是有唯一解的，其它$n-t$个$x_i$都有两解。所以方案数为$2^{n-t}$，贡献就为$2^{i+j-t}$。
当$i\neq j$时，$i+j\geq1,\ t\leq2$，所以$2^{i+j-t}\geq0.5$。
当$i=j$时，$i+j\geq0,\ t\leq1$，依旧有$2^{i+j-t}\geq0.5$。
扩展到$k\geq2$的情况，设选出的位有$k'$位是互不相同的，设为$i,j,l...$，那么方程组中右式为$1$的等式有$k'$个，且$i+j+l+...\geq0+1+2+...=\frac{k(k-1)}{2}\geq k-1\geq t-1$，所以$i+j+l+...-t\geq-1$，贡献$2^{i+j+l+...-t}\geq0.5$。
$k=1$时，显然也成立。
综上，答案要么是整数，要么是一位小数$.5$。

---

其次要注意的是数据范围。答案小于$2^{63}$，那么似乎就有$a_i^k\lt2^{63}$，$a_i\lt\frac{2^{63}}{k}$。
但是个人认为，比如$k=1$，$a_i\lt2^{63}$，但是存在$2^{63}\leq a_i\lt2^{64}$也是可以的，因为毕竟是求平均值，多一位还是可能被拉低到下一位去的。所以应该是$a_i\lt\frac{2^{64}}{k}$（$k=1$需要unsigned long long）。
然而没见到有人这么写的（写范围的都是$a_i\lt\frac{2^{63}}{k}$）...那我就不知道为啥都开的unsigned long long了。
看了下数据，确实最大值是18446727131960884031$>2^{63}$。（答案是$2^{63}-0.5$ 233好强大）

---

考虑怎么做。对$k$分别求解。

$k=1$：
对每一位分别考虑。设某一位为$1$的数有$t$个，为$0$的有$n-t$个，那么选出奇数个该位为$1$的方案数是：$\sum_{i\ is\ odd}C_n^i2^{n-t}$，偶数个的方案数是$\sum_{i\ is\ even}C_n^i2^{n-t}$。
而$C_n^1+C_n^3+C_n^5+...=2^{n-1}=C_n^0+C_n^2+C_n^4...$
也就是选出该位为$1$的数的个数为奇数和偶数的概率是一样的。那么只要$t\geq0$，该位为$1$为$0$的概率是一样的。
所以求一下哪些位上出现过$1$，加起来除以$2$就好了。

$k=2$：
上面说了答案可以写成$\sum_i\sum_jb_ib_j2^{i+j}$。可以直接$\log^2$枚举$i,j$。
$b_i$为$1$的概率和$k=1$时的情况一样，如果存在一个数第$i$位为$1$，那么就是$\frac12$，否则是$0$。所以如果存在数第$i$位不为$0$且存在数第$j$位不为$0$，那么贡献就是$\frac14\times2^{i+j}$。
需要注意的是如果每个数$i,j$位都相同且至少存在一个数满足$i,j$位不为$1$，那么$i,j$为$1$是同时出现的，概率是$\frac12$。

$k\geq3$：
此时$a_i\lt2^{22}$，线性基中的元素个数不超过$22$，所以可以直接$2^{cnt}$枚举线性基中元素集合（设线性基元素个数为$cnt$）。
线性基中每个子集出现的概率都是$2^n\times2^{n-cnt}=\frac{1}{2^{cnt}}$，求出子集异或和$x^k$后除一下即可。
需要注意的是除$2^{cnt}$之前$x^k$是可以超过$2^{63}$的。需要把$x$表示成$\lfloor\frac{x}{2^{cnt}}\rfloor\times2^{cnt}+x\%2^{cnt}$。
因为有$\lfloor\frac{x^k}{2^{cnt}}\rfloor\times x+\lfloor\frac{(x^k\%2^{cnt})\times x}{2^{cnt}}\rfloor=\lfloor\frac{x^{k+1}}{2^{cnt}}\rfloor$。

证明：令$x^k=a\times2^{cnt}+b\ (b<2^{cnt})$，那么等式左边$=ax+\lfloor\frac{bx}{2^{cnt}}\rfloor$，等式右边$=\lfloor\frac{x^k\times x}{2^{cnt}}\rfloor=\lfloor\frac{ax2^{cnt}+bx}{2^{cnt}}\rfloor=ax+\lfloor\frac{bx}{2^{cnt}}\rfloor=左式$。

---

正睿OI联赛停课训练day10AM B

很简单的DP是$f[i][j]$表示当前挂了$i$个人，小R受到$j$次攻击的概率。转移时枚举这次攻击挂了多少人。这样是$O(n^3)$的。

怎么优化呢。因为攻击是无差别的，不妨直接令$f[i][j]$表示第$i$轮时，$i\sim n$受到$j$次攻击的概率。转移为，如果$i$还没出局（那么它受到过$j-1$次攻击），就让他出局并攻击一次剩下所有人；否则如果$i$在之前的$j$次攻击中挂了，就不攻击其他人。
所以有$f[i][j]=f[i-1][j]*(1-p_2^j)+f[i-1][j-1]*p_2^{j-1}$，其中$p_2=1-p$。

---

$\frac ab\ mod\ p\equiv \frac{a\ mod\ (b*p)}{b}$
对于$b\mid a$，$\frac ab\%m=x$
$a=(x+k*m)*b\to a=x*b+k*m*b\to \frac{a\%(m*b)}{b}=x$

---