T1签到

显然答案是

$1-{\mathrm{\Pi }}_{i=1}^n(1-p_i)1-\backslash Pi\_\{i=1\}^\{n\}\backslash left(1-p\_\{i\}\backslash right)$

注意当$n=0n=0$的时候，被砸到的概率为$00$。

T2法法

显然答案就是

T3红球进黑洞

对于$k\in \{0,1\}k\; \backslash in\backslash \{0,1\backslash \}$的部分，提示大体思路应该是是逐位考虑，也就是说对于某一位，只需要知道有多少个元素在这里一位是1就行了，然后乘以相应的2的若干次幂。

T4树上求和

搞出来$dfsdfs$序列后，子树是一段连续的区间，因此是个序列问题，小学老师告诉我们，${(x_i+a)}^2=x_i^2+a^2+2a{x}_i\backslash left(x\_\{i\}+a\backslash right)^\{2\}=x\_\{i\}^\{2\}+a^\{2\}+2\; a\; x\_\{i\}$，显然可以线段树维护，那么你就切掉这道题了。

##T5换个角度思考

查询区间小于等于某个数的个数,如果强制在线的话要写主席树之类的...

然而允许离线，那么可以直接用套路做题了

首先把询问$(I,r,k)(I,r,\; k)$拆成$(1,r,k)(1,r,\; k)$和$(1,1-1,k)(1,1-\; 1,k)$,同时打上对答案产生贡献的标记(前者是$11$,后者是$-1-1$)

那么现在问题就成了:查询前缀小于等于$kk$的个数

把所有询问按照右端点(实际上是$rr$)排序，然后转化为-开始给定一个空序列， 每次往序列末端添加一个数，同时支持查询这个序列小于等于$kk$元素个数

数据范围才$10^{5}10^5$,树状数组维护一下就好了。

##T6暴力出奇迹

不妨看数据范围猜题解

$1\sim 11\; \backslash sim\; 1$

$n\le 10,a_i\le 10^{5}n\; \backslash leq\; 10,\; a\_\{i\}\; \backslash leq\; 10^\{5\}$

发现$nn$很小，不妨暴力枚举区间,然后更新最大值

注意$a_i\le 10^{5}a\_i\le 10^5$,也就是说答案可以到达$10^{10}10^\{10\}$级别，所以你应该使用long long 这种数据类型

$2\sim 22\; \backslash sim\; 2$

$n\le 10^5,\mathrm{\forall }i,j\in [1,n],a_i=a_{j}n\; \backslash leq\; 10^\{5\},\; \backslash forall\; i,\; j\; \backslash in[1,\; n],\; a\_\{i\}=a\_\{j\}$

发现每个数都一模一样，那么选择的区间就是$[1,n][1,n]$

$3\sim 33\; \backslash sim\; 3$

$n\le 10^5,a_i=in\; \backslash leq\; 10^\{5\},\; a\_\{i\}=i$

迷之部分分，出题人并没想怎么做

$4\sim 44\; \backslash sim\; 4$

$200\le n\le 10^5,\mathrm{\forall }i\in [1,100],a_{i}200\; \backslash leq\; n\; \backslash leq\; 10^\{5\},\; \backslash forall\; i\; \backslash in[1,100],\; a\_\{i\}$ 是随机数, $\mathrm{\forall }j\in [101,n],a_j=0\backslash forall\; j\; \backslash in[101,\; n],\; a\_\{j\}=0$

发现$[101,n][101,\; n]$实际上没啥用，也就是说成了一个$n\le 100n\le 100$的问题，$O(n^2)O(n^2\; )$就行

$5\sim 105\; \backslash sim\; 10$

不妨看一下最大值：$10^5\times (10^5\times 10^5)=10^{15}10^\{5\}\; \backslash times\backslash left(10^\{5\}\; \backslash times\; 10^\{5\}\backslash right)=10^\{15\}$

用 long long 存一下就好

如果固定右端点,然后往左扩展,那么取值只有$O(logV)O(log\; V)$种,其中$VV$是最大值

证明

不妨拆位考虑，每一位只会从$11$变为$00$,或者保持$00$,因此只有$O(logV)O(log\; V)$种取值

那么从左往右枚举右端点，对于每一个值， 维护最左侧的端点就好了

##T7简单

前置技能

森林中连通块个数的$TT$存在等式: $T=n-mT\; =\; n-m$

证明:每添加一条边，就会合并两个连通块，相应的，连通块的个数就会少一个

根据期望的线性性，可得:$E(T)=E(n)-E(m)E(T)=\; E(n)-\; E(m)$

于是问题就转化为了计算$E(n)E(n)$和$E(m)E(m)$

为了方便起见，设$P_{u}P\_u$表示$uu$的存在的概率

于是对$P_{u}P\_u$做前缀和数组$S_{p}S\_p$后,可得，$E\left(n_{[l,r]}\right)=S_{p,}-S_{p_{l-1}}E\backslash left(n\_\{[l,\; r]\}\backslash right)=S\_\{p,\}-S\_\{p\_\{l-1\}\}$

之后只需要考虑$E(m)E(m)$如何计算，显然有:

$E\left(m_{[l,r]}\right)={\sum }_{(u,v)\in \mathbb{E}\wedge \omega \in [l,r]}{\sum }_{n\in \in [l,r]}{p}_u\cdot p_{v}E\backslash left(m\_\{[l,\; r]\}\backslash right)=\backslash sum\_\{(u,\; v)\; \backslash in\; \backslash mathbb\{E\}\; \backslash wedge\; \backslash omega\; \backslash in[l,\; r]\}\; \backslash sum\_\{n\; \backslash in\; \backslash in[l,\; r]\}\; p\_\{u\}\; \backslash cdot\; p\_\{v\}$

于是可以暴力的把每一条$(u,v)\in \mathbb{E}(u,\; v)\; \backslash in\; \backslash mathbb\{E\}$的边看成一个点 $(u,v)(u,v)$,它的权值是$p_u{}^{\ast }{p}_{v}p\_\{u\}\{\; \}^\{*\}\; p\_\{v\}$。

之后相当于询问一个矩形内的点的权值和，这显然就是一个二 维数点问题，可以使用离线后树状数组或主席树或树套树乱搞

T8论如何出一道水题

对于相邻的两个数字$x,x+1x,x+\; 1$来说，有:

$\gcd (x,x+1)=\gcd (x+1-x,x)=\gcd (1,x)=1\backslash operatorname\{gcd\}(x,\; x+1)=\backslash operatorname\{gcd\}(x+1-x,\; x)=\backslash operatorname\{gcd\}(1,\; x)=1$

所以答案就是：

$n+\max (n-1,1)n+\backslash max\; (n-1,1)$

T9给给

根据期望的线性性，可得知$E(U)={\sum }_{i=1}^{n}1\times p(i)E(U)=\backslash sum\_\{i=1\}^\{n\}\; 1\; \backslash times\; p(i)$

也就是说只需要计算每一个点至少被选中一次的概率就行了，设第$ii$个点的这个概率为$p(i)p(i)$

然而这个不太好算，不妨算另一个东西

设$q(i)q(i)$表示第$ii$个点，在这$kk$次选择中都没有被染色的概率，因为$p(i)p(i)$和$q(i)q(i)$是互斥事件, 所以$p(i)+q(i)=1p(i)\; +q(i)=1$,即 $p(i)-1-q(i)p(i)-1-\; q(i)$

$kk$次都没有被染色的意义是，每次都不会选择跨过这个点的路径，这个可以通过一次dfs计算每个节点的size后乘一 乘就行了

于是就做完了

T10 div.2A

$\left(\begin{array}{c}t+k-1\\ k-1\end{array}\right)=\left(\begin{array}{c}t+k-1\\ t\end{array}\right)=\frac{(t+k-1)!}{t!(k-1)!}\backslash left(\backslash begin\{array\}\{c\}t+k-1\; \backslash \backslash \; k-1\backslash end\{array\}\backslash right)=\backslash left(\backslash begin\{array\}\{c\}t+k-1\; \backslash \backslash \; t\backslash end\{array\}\backslash right)=\backslash frac\{(t+k-1)\; !\}\{t\; !(k-1)\; !\}$

由于$t\le {}_2(n)t\; \backslash leq\; \backslash log\; \_\{2\}(n)$，因此可以直接预处理后再做

时间复杂度：$O(n)O(n)$

其他疑问可加以下交流群（加入一个即可啦~）

牛客多校算法训练营1：453799454

牛客全国算法训练营2：330766563

牛客多校算法训练营3：934889305