「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$ 的贡献(注意最多产生一次)

「2017 山东三轮集训 Day5」Dark

显然答案是:

$$
m^{\sum_{d|n}\left(\frac{n!}{(d!)^{\frac{n}{d}}\left(\frac{n}{d}\right)!}\right)\bmod {(p-1)}} \bmod {p}
$$

可以发现,$p-1=2 \times 13 \times 5281 \times 7283$,对于每一个质数都跑一遍上式即可

「2017 山东三轮集训 Day6」A

显然答案就是:

$$
\sum_{i=0}^{n}[2|i] {n \choose i} {n \choose n-i}=\sum_{i=0}^{n}[2|i] {n \choose i}^2
$$

考虑卢卡斯定理,则:

$$
\sum_{2|i} {n \choose i}^2 \equiv \sum_{2|i} \left( \sum_{j} {d_j \choose i} \right)^2 \pmod {1000003}
$$

「2017 山东三轮集训 Day7」Easy

考虑把所有的查询都离线下来,都扔到线段树上,然后跑一下虚树就行了

「2017 山东三轮集训 Day7」Normal

设 $A(x)$ 是走的步数的生成函数,则答案的生成函数 $F(x)$ 为:

$$
F(x)=\sum_{i}[X|i]{T \choose i}A(x)^i
$$

考虑单位根反演,只需要把 $\omega_X^{0 \sim X-1}$ 都代入,答案就是:

$$
F(x)=\frac{1}{X}\sum_{i=0}^{X-1}(1+\omega_{X}^{i}A(x))^T
$$

由于 $T=2^{k}$,所以直接快速幂即可