数学方向琐记

一些和数学相关的有趣问题，简单和困难的都有。

The 3rd Universal Cup. Stage 13, K

题意简述：长度为 $n$ 的序列，每个元素在 $[0, m)$ 中随机，求序列期望 mex，对 998244353 取模。

期望转总和，然后算贡献。需要求 mex 不小于 $i$ 的方案数，即算 $[0, i)$ 中每个元素都出现的方案数，这里考虑容斥，即钦定 $k$ 个数不能出现。

$$ \begin{aligned} m^n\cdot \text{Ans} &= \sum_{i=1}^{m} \sum_{k=0}^{i}\binom{i}{k}(m-k)^n(-1)^k \\ &= \sum_{k=0}^{m}(-1)^k(m-k)^n\sum_{i=\max(1,k)}^m\binom{i}{k} \\ &= m^{n+1} + \sum_{k=1}^m(-1)^k(m-k)^n\binom{m+1}{k+1} \end{aligned} $$

注意到 $\binom{m+1}{k+1}(-1)^k$ 是类似二项式系数的形式，考虑把他们合到一起去。

我们有 $[\frac{x^n}{n!}]\exp(px)=p^n$，因此：

$$ \begin{aligned} m^n\cdot \text{Ans} &= m^{n+1} \red{-} \sum_{i=1}^m (-1)^{\red{i+1}}([\frac{x^n}{n!}]e^{(m-i)x})\binom{m+1}{i+1} \\ &= [\frac{x^n}{n!}](m^{n+1} - \sum_{i=1}^m (-1)^{i+1}(e^{((m+1)-(i+1))x})\binom{m+1}{i+1}) \\ &= [\frac{x^n}{n!}](m^{n+1} - \sum_{i=0}^{m+1} (-1)^{i}(e^{(m+1-i)x})\binom{m+1}{i} - (m+1)e^{mx} + e^{(m+1)x}) \end{aligned} $$

逆用二项式定理得到：

$$ \begin{aligned} m^n\cdot \text{Ans} &= [\frac{x^n}{n!}](m^{n+1} - (e^x-1)^{m+1} - (m+1)e^{mx} + e^{(m+1)x}) \\ &= m^{n+1}-(m+1)m^n + (m+1)^n - \blue{[\frac{x^n}{n!}](e^x-1)^{m+1}} \end{aligned} $$

蓝色这个柿子咋打开呢？相信身经百战的你一定发现了这就是第二类斯特林数的生成函数：

$$ {n \brace k} = \frac{1}{k!}[\frac{x^n}{n!}](e^x-1)^k $$

因此有

$$ \text{Ans}=\frac{(m+1)!{n \brace m+1}+(m+1)^n}{m^n}-1 $$

$O(n^2)$ 递推即可。

Codeforces Round 979 (Div. 2), E

怎么又是 mex 题啊

这是一个重度魔怔做法。我们直接跳到最后一步，详细信息可以看我写的 sol。

相当于有 $f(n,m)=\sum_{i=0}^{n-1}z^i\binom{i}{m}$，其中 $z$ 是一个不为 $1$ 的常数，我们需要求出某一行（即：$n$ 均相同）的值。

还是考虑拆组合数：

$$ \begin{aligned} f(n,m)&=\sum_{i=0}^{n-1}z^i[x^m](x+1)^i \\ &= [x^m]\sum_{i=0}^{n-1}z^i(x+1)^i \\ &= [x^m]\frac{1-(z(x+1))^n}{1-z(x+1)} \end{aligned} $$

多项式求逆即可 $O(m \log m)$ 求一行。

cxy 说可以找整式递推做到线性，先咕了。

upd: 会了。

不用啥高深的科技，我们直接考虑拆组合数。

$$ \begin{aligned} f(n,m)&=\sum_{i=0}^{n-1}z^i\binom{i}{m} \\ &= \sum_{i=0}^{n-1}z^i(\binom{i-1}{m-1}+\binom{i-1}{m}) \\ &= (z\sum_{i=0}^{n-1}z^i\binom{i}{m-1})+(z\sum_{i=0}^{n-1}z^i\binom{i}{m})-z^n(\binom{n-1}{m}+\binom{n-1}{m-1}) \\ &= z\cdot f(n, m-1)+z\cdot f(n,m)-z^n(\binom{n-1}{m}+\binom{n-1}{m-1}) \end{aligned} $$

又因为 $z\neq 1$，故有

$$ f(n,m)=\frac{z\cdot f(n,m-1)-z^n(\binom{n-1}{m}+\binom{n-1}{m-1})}{1-z} $$

$O(m)$ 递推即可。

U 群看到的题 (1)

“这个柿子有四种推法，你知道么？”

题意：证明 $\sum\limits_{i=1}^n\binom{n}{i}(-1)^{i-1}\frac{1}{i}=H_n$，即调和数第 $n$ 项。

法 1：组合意义

[TBD]

法 2：大力出奇迹

[TBD]

法 3：积分

这个 $\frac{1}{i}$ 看着就让人很不爽，考虑用积分代换掉！

$$ \begin{aligned} \sum\limits_{i=1}^n\binom{n}{i}(-1)^{i-1}\frac{1}{i} &= \sum_{i=1}^n\binom{n}{i}(-1)^{i-1}\int_0^1x^{i-1}\text{d} x \\ &= \int_0^1\sum_{i=1}^n\binom{n}{i}(-x)^{i-1} \text{d}x \\ &= \int_0^1 -\frac{1}{x}(\sum_{i=0}^n \binom{n}{i}(-x)^i-1)\text{d}x \\ &= \int_0^1-\frac 1 x((1-x)^n-1)\text dx \\ &= \int_0^1\frac{1-x^n}{1-x}\text dx \\ &= \sum_{i=0}^{n-1} \int_0^1 x^i \text dx \\ &= \sum_{i=0}^{n-1} \frac{1}{i+1}\\ &= H_n &\square \end{aligned} $$

法 4：GF

[TBD]

【清华集训 2014】sum

给定 $n,r$，求 $\sum_{i=1}^{n}(-1)^{i\sqrt{r}}$。

直接做并不是很好做，考虑把幂消掉。

$$(-1)^x=1-2(x\ \text{mod}\ 2)$$

因此有

$$ \sum_{i=1}^{n}(-1)^{i\sqrt{r}} = \sum_{i=1}^n 1-2\lfloor i\sqrt r\rfloor + 4 \lfloor \frac{i\sqrt r}{2} \rfloor \\ $$

需要求的问题其实是 $\sum_{i=1}^n\frac{a\sqrt r+b}{c}$。考虑一个类似类欧的东西。

$$ \begin{aligned} t&:=\frac{a\sqrt r+b}{c} \\ f(n,a,b,c) &:= \sum_{i=1}^n \lfloor ti\rfloor = \sum_{i=1}^n \sum_{j=1}^{\lfloor ti\rfloor} 1 \end{aligned} $$

考虑交换求和次序。特判掉 $r$ 是整数的情况，则有：

$$ \begin{aligned} &j \le \lfloor ti\rfloor < ti \\ \implies &i > \frac{j}{t} \ge \lfloor \frac{j}{t} \rfloor \end{aligned} $$

因此

$$ \begin{aligned} f(n,a,b,c)&= \sum_{j=1}^{\lfloor nt \rfloor}(n-\lfloor\frac{j}{t}\rfloor) \\ &= n\cdot \lfloor nt \rfloor -\sum_{j=1}^{\lfloor nt \rfloor}\lfloor \frac{1}{t}\cdot j \rfloor \\ &= n\cdot \lfloor nt \rfloor - f(n\cdot \lfloor nt \rfloor,ac,-bc,a^2r-b^2) \end{aligned} $$

为了保证复杂度，在 $t \ge 1$ 的时候要先将整数部分去掉。这样至多递归两次的时候 $n$ 可以减半。

证明：考虑 $t \le 0.5$ 时一次就可以减半；否则 $\frac{1}{t} < 2$，故有 $\{\frac{1}{t}\}=\frac{1}{t}-1$， 两次递归后 $n \gets n \cdot t \cdot (\frac1t-1)=n(1-t)<0.5n$。

这里有一个很玄学的事情：递归下去的时候 $a,b,c$ 一直增大，一下子就爆 long long 了。于是我们把 $a,b,c$ 除掉他们的 $\gcd$。打个表 可以发现在题目的数据范围内不会爆，太深刻了！

一个有趣的结论

定义 $\text{val}(F(x))$ 为 $F(x)$ 各项系数 $\gcd$，有：

$$ \text{val}\left(\prod_{i=1}^n F_i(x)\right) = \prod_{i=1}^n\text{val}(F_i(x)) $$

证明：

不妨记 $x = \text{val}\left(\prod_{i=1}^n F_i(x)\right),\ y = \prod_{i=1}^n\text{val}(F_i(x))$。

• 显然，$y \mid x$。
• 假设 $p\cdot y \mid x\ (p \in P)$，考虑将 $F_i(x)$ 每项系数都除以 $\text{val}(F_i(x))$；考虑每个多项式在模 $p$ 意义下的系数，由于之前除的是 $\gcd$ 所以一定存在一项非 $0$，将每个多项式非 $0$ 最高位乘起来，设结果为 $kx^t$，则 $[x^t]\prod_{i=1}^nF_i(x) \equiv k \not \equiv 0 \pmod p$，故 $p\cdot y \nmid x$，矛盾。
• 综上，$x=y$。$\square$

多重背包二进制分组做法复杂度分析

事实上，我们可以分析到比根号 log 物品总重量更优秀！

记 $t_i$ 表示大小为 $i$ 的物品的数量，我们有 $W=\sum_ii\cdot t_i$。下面证明，二进制分组实现的多重背包复杂度为 $W\sqrt W$。

显然，总运算量为 $c = W\sum_i \log_2 t_i$。由于 $\lfloor\log_2 x\rfloor+1 = \sum_{p \ge 0}[2^p \le x]$，我们有：

$$ \begin{aligned} \sum_i \log_2t_i &\le \sum_i\sum_p [2^p \le t_i] \\ &=\sum_p \sum_i [\lfloor\frac{t_i}{2^p}\rfloor>0] \end{aligned} $$

同时，$\sum_ii\lfloor\frac{t_i}{2^p}\rfloor\le\frac{W}{2^p}$，故有：

$$ \sum_i \log_2t_i = O(\sum_p\sqrt{\frac{W}{2^p}})=O(\sqrt W) $$

故总复杂度为 $O(W\sqrt W)$。$\square$