牛客练习赛107-题解

A.注意到$\mathrm{\forall }n>m,n!modm=0\backslash forall\; n>m\; ,\; n!\; \backslash space\; mod\; \backslash space\; m\; =\; 0$,又有$10!=3628800>10^{6}10!\; =\; 3628800\; >\; 10^6$,故对于$n\ge 10n\backslash ge\; 10$,$(n!)!modm=0(n!)!\; \backslash space\; mod\; \backslash space\; m\; =\; 0$. 然后预处理所有的,$x!modmx!\; \backslash space\; mod\; \backslash space\; m$的值。每次对于小于$1010$的$nn$，暴力计算$n!n!$的值，并查表得到$(n!)!modm(n!)!\; \backslash space\; mod\; \backslash space\; m$的值。

B.注意到对于排列$PP$，若$P_1=1P\_\{1\}\; =\; 1$，则必有$PP$的前缀最小值变化次数($f(P)f(P)$)等于$11$。所以当$P_1=1P\_\{1\}\; =\; 1$时，取$Q_1=1Q\_\{1\}\; =\; 1$，则也有$Q_1^{\mathrm{\prime }}=1Q\text{'}\_\{1\}\; =\; 1$，此时$max(f(Q),f(Q^{\mathrm{\prime }}))=1max(f(Q),f(Q\text{'}))\; =\; 1$，显然取到最小值。 在$P_1\mathrm{\ne }1P\_\{1\}\; \backslash neq\; 1$时，$Q_{1}Q\_\{1\}$和$Q_1^{\mathrm{\prime }}Q\text{'}\_\{1\}$必有一个不为$11$，则答案至少为$22$（因为第一个位置和$11$所在的位置必然产生贡献），考虑构造答案为$22$的$QQ$。不妨令$Q_1^{\mathrm{\prime }}=1Q\text{'}\_\{1\}\; =\; 1$，则有$f(Q^{\mathrm{\prime }})=1f(Q\text{'})\; =\; 1$，此时$Q_{P_1}=1Q\_\{P\_\{1\}\}\; =\; 1$已经决定，其余未决定。则令$Q_1=2Q\_\{1\}\; =\; 2$，那么$f(Q)f(Q)$必然为$22$。剩余的位置可以随便填。

C.分$k\le \sqrt{n}k\; \backslash le\; \backslash sqrt\{n\}$和$k>\sqrt{n}k\; >\; \backslash sqrt\{n\}$考虑。 $k\le \sqrt{n}k\backslash le\; \backslash sqrt\{n\}$时，可以直接暴力计算答案，复杂度为$\sum lo{g}_{k}n\backslash sum\{log\_\{k\}\{n\}\}$,不超过$\sqrt{n}log(n)\backslash sqrt\{n\}log(n)$. $k>\sqrt{n}k>\backslash sqrt\{n\}$时，注意到此时转换过去的数必为$22$位数，且低位为$nmodk=n-k\ast \lfloor \frac{n}{k}\rfloor n\backslash space\; mod\; \backslash space\; k\; =\; n-k*\backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor$，高位为$\lfloor \frac{n}{k}\rfloor \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor$,此时$k_2=1+max(n-k\ast \lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor )k\_\{2\}\; =\; 1+max(n-k*\backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor\; ,\; \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor)$。考虑进行整除分块。不妨设$x=\lfloor \frac{n}{k}\rfloor x=\backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor$，考虑$xx$所有对应的$kk$: $n-k\lfloor \frac{n}{k}\rfloor \ge \lfloor \frac{n}{k}\rfloor ⟺n\ge (k+1)\lfloor \frac{n}{k}\rfloor ⟺\frac{n}{k+1}\ge \lfloor \frac{n}{k}\rfloor ⟺\lfloor \frac{n}{k+1}\rfloor =\lfloor \frac{n}{k}\rfloor \backslash qquad\; \backslash space\; \backslash space\; \backslash space\; n-k\backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor\; \backslash ge\; \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor\; \backslash \backslash \; \backslash iff\; n\; \backslash ge\; (k+1)\backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor\; \backslash \backslash \; \backslash iff\; \backslash frac\{n\}\{k+1\}\; \backslash ge\; \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor\; \backslash \backslash \; \backslash iff\; \backslash lfloor\; \backslash frac\{n\}\{k+1\}\; \backslash rfloor\; =\; \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor$ (最后一步可以脑补一下数轴） 由此，对于一个固定的$xx$和$k\in [l,r]k\; \backslash in\; [l,r]$,仅有端点$rr$处选择$k_2=\lfloor \frac{n}{k}\rfloor k\_\{2\}\; =\; \backslash lfloor\; \backslash frac\{n\}\{k\}\; \backslash rfloor$,接下来就可以很快乐的整除分块了。

D.早就被猜到了，但是$DD$过的比$BB$多还是有点出乎意料… 对于一对$(i,j)(i,j)$，进行一次操作等价于把所有的二进制位的$11$都尽量向$jj$位置靠拢。形式化地，对于某个二进制位$xx$，令$i_x,j_{x}i\_\{x\},j\_\{x\}$表示$i,ji,j$位置上的数的该位的值，则若$i_x,j_{x}i\_\{x\},j\_\{x\}$中有两个$11$或者零个$11$，执行操作后不变，否则变为$i_x=0,j_x=1i\_\{x\}=0,j\_\{x\}=1$。 对于总体来说，也是一样的。每个二进制位将所有的$11$尽量向后靠拢。形式化地，假设某个二进制位共有$pp$个$11$，则后$pp$个数在该位为$11$，前$n-pn-p$个数在该位为$00$。

E.读完就会做的题。本来这题时限$3s3s$,$m=2e5,k=10m=2e5,k=10$,哪怕在这种情况下std也是能跑过的，结果放宽限制发现大家还是被卡常数了，难受。 不妨令$P_{u}P\_\{u\}$表示$LL$在$uu$的子树内的概率，令$S_{u}S\_\{u\}$表示$uu$子树内所有节点的$p_{u}p\_\{u\}$的和。不难发现这件事等价于所有的选择的点全部在$uu$的子树内，所以$P_u=(\frac{S_u}{S_1}{)}^{k}P\_\{u\}\; =\; (\backslash frac\{S\_\{u\}\}\{S\_\{1\}\})^\{k\}$。 令$An{s}_{u}Ans\_\{u\}$代表$LL$恰好为$uu$的概率，则$An{s}_u=P_u-\sum P_v=\frac{S_u^k-\sum S_v^k}{S_1^k}Ans\_\{u\}\; =\; P\_\{u\}\; -\; \backslash sum\{P\_\{v\}\}\; =\; \backslash frac\{S\_\{u\}^k-\backslash sum\{S\_\{v\}^k\}\}\{S\_\{1\}^k\}$，其中$vv$是$uu$的儿子们。最终的期望为$\sum u\ast An{s}_u\backslash sum\{u*Ans\_\{u\}\}$。 由于可以把$S_1^{k}S\_\{1\}^k$留在最后统一除，所以先抛掉这部分。考虑每个$S_u^{k}S\_\{u\}^k$的贡献，不难发现它在$uu$处的贡献为$u\ast S_u^{k}u*S\_\{u\}^k$，而在$f_{u}f\_\{u\}$处的贡献为$-f_u\ast S_u^k-f\_\{u\}*S\_\{u\}^k$，其中$f_{u}f\_\{u\}$为$uu$的父亲，在其余各点处没有贡献。所以最后答案等于$\sum (u-f_u)\ast S_u^k\backslash sum\{(u-f\_\{u\})*S\_\{u\}^k\}$。注意到$u-f_{u}u-f\_\{u\}$是个常数，而每次更新只会更新该节点到根上的所有点的$S_{u}S\_\{u\}$，故直接采用树剖线段树维护。线段树维护区间$u-f_{u}u-f\_\{u\}$乘以$S_{u}S\_\{u\}$的$00$次至$kk$次幂的和，每次打标记时通过组合数转移即可。时间复杂度$O(m{k}^{2}lo{g}^2(n))O(mk^2log^2(n))$，虽然看起来很大，但是跑起来很快。 本题还可以离线询问，线段树合并做到$m{k}^{2}log(n)mk^2log(n)$（口胡的，没写过） Bonus:你能做的更快吗？

F.假设枚举最小值$MM$，则对应的EGF是$({\sum }_{i=0}^{k-1}\frac{x^i}{i!}{)}^{M-1}\times ({\sum }_{i=0}^n\frac{x^i}{i!}{)}^{m-M}\times ({\sum }_{i=k}^n\frac{x^i}{i!})(\backslash sum\_\{i=0\}^\{k-1\}\{\backslash frac\{x^i\}\{i!\}\})^\{M-1\}\; \backslash times\; (\backslash sum\_\{i=0\}^\{n\}\{\backslash frac\{x^i\}\{i!\}\})^\{m-M\}\; \backslash times\; (\backslash sum\_\{i=k\}^\{n\}\{\backslash frac\{x^i\}\{i!\}\})$,所求答案为该EGF的$x^{n}x^n$项系数乘以$\frac{n!}{m^n}\backslash frac\{n!\}\{m^n\}$。

不妨令$A(x)={\sum }_{i=0}^{k-1}\frac{x^i}{i!}A(x)\; =\; \backslash sum\_\{i=0\}^\{k-1\}\{\backslash frac\{x^i\}\{i!\}\}$ , $B(x)=({\sum }_{i=0}^n\frac{x^i}{i!}),C(x)={\sum }_{i=k}^n\frac{x^i}{i!}B(x)\; =\; (\backslash sum\_\{i=0\}^\{n\}\{\backslash frac\{x^i\}\{i!\}\})\; ,\; C(x)\; =\; \backslash sum\_\{i=k\}^\{n\}\{\backslash frac\{x^i\}\{i!\}\}$,则答案等于$\frac{n!}{n^m}\times [x^n]{\sum }_{M=1}^{m}C(x)\times A(x{)}^{M-1}\times B(x{)}^{m-M}\times M\backslash frac\{n!\}\{n^m\}\; \backslash times\; [x^n]\; \backslash sum\_\{M=1\}^\{m\}\{C(x)\; \backslash times\; A(x)^\{M-1\}\; \backslash times\; B(x)^\{m-M\}\; \backslash times\; M\}$,而后面那个多项式等于

$C(x)\frac{mA(x{)}^{m+1}-B(x)(m+1)A(x{)}^m+B(x{)}^{m+1}}{(A(x)-B(x){)}^2}C(x)\backslash frac\{mA(x)^\{m+1\}\; -\; B(x)(m+1)A(x)^m\; +\; B(x)^\{m+1\}\}\{(A(x)-B(x))^2\}$，注意到$C(x)=B(x)-A(x)C(x)=B(x)-A(x)$,则上式等于$\frac{mA(x{)}^{m+1}-B(x)(m+1)A(x{)}^m+B(x{)}^{m+1}}{C(x)}\backslash frac\{mA(x)^\{m+1\}\; -\; B(x)(m+1)A(x)^m\; +\; B(x)^\{m+1\}\}\{C(x)\}$,然后可以使用任意你喜欢的多项式技巧去计算这个式子了。这题时限似乎不紧吧。