tmp

tmp

---

contest 5A

description

初始给定一个数组$A$，进行$T$次操作，每次操作以$p_i$的概率在$A_i$上加一，求$E(\sum_{i=1}^n(A_i')^k)$，对$998244353$取模
$n<=10,k<=50,T<=10^{18},A_i\in[0,998244352]$

solution

首先，这$n$个数可以分开考虑，每个数的贡献是独立的

$$ans=\sum_{i=1}^nE(A_i+delta_i)^k\\$$
以下分别考虑每一个位置的答案，枚举在$A_i$处加了几：
$$ans=(A+delta)^k\\=\sum_{i=0}^T\frac{\binom{T}{i}}{2^T}p^i(1-p)^{T-i}(A+i)^k$$
考虑到k次方相当不好处理，又发现$\binom{n}{m}=\frac{n!}{m!(n-m)!}$，如果能把k次方化为下降幂是最好的。

---

下面先讲一下下降幂:
不妨记

$$x^\underline k=\prod_{i=0}^k (x-i)$$
下降幂二项式定理： $$(x+y)^\underline n=\sum_{i=0}^nx^ \underline iy^\underline {n-i} \binom{n}{i}$$
下降幂与第二类斯特林数的关系：
$$x^k=\sum_{i=0}^kS(k,i)x^\underline i$$
其中$S(n,m)$指的是第二类斯特林数

---

开始推导式子：

$$\begin{align*} ans =& \frac{1}{2^T}\sum_{i=0}^T{\binom{T}{i}}p^i(1-p)^{T-i}(A+i)^k\\ =& \frac{1}{2^T}\sum_{i=0}^T{\binom{T}{i}}p^i(1-p)^{T-i}\sum_{r=0}^kS(k,r)(A+i)^\underline r\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{i=0}^T{\binom{T}{i}}p^i(1-p)^{T-i}S(A+i)^\underline r\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{i=0}^T{\binom{T}{i}}p^i(1-p)^{T-i}\sum_{m=0}^r\binom{r}{m}A^\underline m i^\underline {r-m}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}\sum_{i=0}^T\binom{T}{i}p^i(1-p)^{T-i}i^\underline {m}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}\sum_{i=0}^T\frac{T!}{i!(T-i)!}p^i(1-p)^{T-i}\frac{i!}{(i-m)!}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}\sum_{i=0}^T T^\underline{i}p^i(1-p)^{T-i}\frac{1}{(i-m)!}\\ \end{align*}$$
当$i<m$时，$\frac{1}{(i-m)!}$不存在
$$\begin{align*} ans =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}\sum_{i=m}^T T^\underline{i}p^i(1-p)^{T-i}\frac{1}{(i-m)!}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}\sum_{i=0}^{T-m} T^\underline{i}p^{i+m}(1-p)^{T-m-i}\frac{1}{i!}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}p^m\sum_{i=0}^{T-m} \binom{T}{i}p^{i}(1-p)^{T-m-i}\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\binom{r}{r-m}A^\underline {r-m}p^m\\ =& \frac{1}{2^T}\sum_{r=0}^kS(k,r)\sum_{m=0}^r\frac{r!}{m!(r-m)!}A^\underline {r-m}p^m\\ \end{align*}$$
这显然就是一个卷积的形式，只剩最后一步：求出所有的$S(k,i)$!
根据第二类斯特林数的组合意义 $$S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n$$
拆开组合数后，又是卷积形式，直接FFT即可

---

contest 7C

description

定义一个数是好数当且仅当质因数分解后$x=\prod_{i=1}^kp_i^{a_i}$，$\forall i\in[1,k]$, $a[i]\mod2=1$，求1到n中有多少好数
$n<=10^{10}$

solution

第一眼看到这道题，min25筛呀，不是积性函数？
事实上，$f(x)=[x\in Good]$是积性函数！！
回顾一下积性函数定义

$$\forall a,b \wedge gcd(a,b)=1,f(a*b)=f(a)*f(b)$$
再回顾一下完全积性函数定义 $$\forall a,b,f(a*b)=f(a)*f(b)$$
以后不能忘积性函数要选互质的两个数！！

---

下面进入$min25$筛时刻：
当$x\in Prime$，一定有$f(x)=1$
在$min25$筛中，$g(n,j)=\sum_{i=1}^n[i\in Prime\quad or\quad min(p)>p_j]f(i)$
只需要求$g(x,\left| Prime\right|))$，那太方便了，整除分块的处理都不用，直接

$$g(x,|Prime|)=\sum_{i=1}^x[i\in Prime]$$
直接用$min25$筛的套路即可
最后发现暴力轻松碾压min25，感受特别不好

---