山东集训题

「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set

线性基贪心

「2017 山东一轮集训 Day7」逆序对

考虑从小到大插入 $1 \sim n$，显然对于数字 $i$，会贡献 $0 \sim i-1$ 个逆序对

也就是说求：

$$
[x^k] \prod_{i=1}^{n} (1 + x+ x^2 + \cdots + x^{i-1})=[x^k]\frac{\prod_{i=1}^{n}(1-x^i)}{(1-x)^n}
$$

有：

$$
\frac{1}{(1-x)^n}=\sum_{i=0}^{\infty} {n-1+i \choose n-1} x^i
$$

考虑分子，相当于求从 $i$ 个数中挑出若干个，使得和为 $j$ 的方案数，如果选了 $k$ 个，则系数为 $(-1)^k$

也就是只需要处理出，从 $i$ 个数中选出 $j$ 个数的方案数即可

实际上是给定 $n$ 个数字 $1,2,3, \cdots, n$，求从中选出 $j$ 个互不相同的数字的方案数，满足它们的和为 $k$

设 $f_{i,j}$ 表示选了 $i$ 个数，和为 $j$ 的方案数，那么考虑是否有 $1$，可以得到：

$$
f_{i,j}=f_{i-j,j}+f_{i-j,j-1}-f_{i-(n+1),j-1}
$$

「2017 山东二轮集训 Day1」第二题

实际上就是这个题 ~~搬题赚大钱~~

考虑操作翻转过来，变为每次拆一些竹子，先把笛卡尔树搞出来

设 $f_u$ 表示拆完以 $u$ 为根的子树的最少次数，$g_u$ 表示在最少次数的前提下，还能顺便拆多少

转移就直接贪心的能拿就拿即可

「2017 山东二轮集训 Day1」第三题

不妨手玩一下关于 $\text{lcm}$ 的性质……

$$
\text{lcm}(a,b)=\frac{ab}{\gcd(a,b)}
$$

$$
\text{lcm}(a,b,c)=\frac{abc\gcd(a,b,c)}{\gcd(a,b)\gcd(b,c)\gcd(a,c)}
$$

推广到更一般的情况，即一个集合 $S$ 的 $\text{lcm}$：

$$
\text{lcm}(S)=\prod_{\emptyset \ne T \subseteq S} \gcd(T)^{\left( (-1)^{\mid T \mid + 1} \right)}
$$

之后就要去看一下斐波那契数列的性质咯

通过这道题可以学习到一个关于斐波那契数列的很重要的性质：

$$
\gcd(f_i,f_j)=f_{\gcd(i,j)}
$$

于是就可以化简一下式子咯：

$$
\begin{aligned} &\text{lcm}(f_{a_1},f_{a_2},f_{a_3},f_{a_4},\cdots,f_{a_n}) \\ =&\prod_{\emptyset \ne T \subseteq S} \gcd({f_{T}})^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ \end{aligned}
$$

然而这个还是不太好做……因为有一个 $[\gcd(S)=d]$ 的限制……

然而这个可以想到莫比乌斯反演那一套理论

$$
f=g \times 1 \Leftrightarrow g=f \times \mu
$$

考虑在 $\prod$ 意义下的莫比乌斯反演……

$$
f_n=\prod_{d \mid n} g_d \Leftrightarrow g_n=\prod_{d \mid n}f_d^{\mu(\frac{n}{d})}
$$

当然如果只是要计算 $g$的话，有：

$$
f_n=\prod_{d \mid n} g_d \Rightarrow g_n=\frac{f_n}{\prod_{d \mid n \wedge d \ne n}g_d}
$$

然后就可以通过枚举倍数来计算出 $g$ 了

于是现在式子就相当于这个了：

$$
\begin{aligned} &\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} \left(\prod_{d \mid \gcd(T)}g_d\right)^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{d} g_d^{\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)}(-1)^{\mid T \mid + 1}} \end{aligned}
$$

考虑一个 $g_d$ 对答案的贡献，也就是指数上那个玩意，即：

$$
\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1}
$$

显然是实际有用的 $T$ 的并集是 $S’={x \mid \forall x \in S \wedge d \mid x}$

假设 $\mid S’ \mid = n$，则有：

$$
\begin{aligned} &\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1} \\ =&\sum_{i=1}^{n} {n \choose i} (-1)^{i+1} \\ =&(-1) \left(\sum_{i=1}^{n}{n \choose i}(-1)^{i}\right) \\ =&(-1) \left((1-1)^n-{n \choose 0} (-1)^{0}\right) \\ =&[n \ne 0] \end{aligned}
$$

也就是说，对于一个 $g_d$，只要 $\exists x \mid a_i$，那么 $g_d$ 就会对答案产生 $1$ 的贡献（注意最多产生一次）