【互测】20/05/27

本文主要是介绍【互测】20/05/27，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

瑠璃色の物語 - By 大神可可

• 考虑 $S$ 为可重集合，令 $c(S)={\sum }_{i\in S}{c}_i,v(S)={\sum }_{i\in S}{v}_i$，考虑最后的答案是什么
  $$\begin{gathered} k![(xy{)}^k]\prod e^{v(S)x^{c(S)}y}\ast e^y \\ =k![(xy{)}^k]e^{{\sum }_{S}v(S)x^{c(S)}y+y} \\ [x^k](\sum _{S}v(S)x^{c(S)}+1{)}^k \end{gathered}$$
  首先考虑求这么一个东西
  $$coe{f}_k=\sum _{c(S)=k}v(S)$$
  这个其实是
  $$\begin{gathered} \prod _i\frac{1}{1-v_i{x}^{c_i}} \\ =\exp (\sum \ln (\frac{1}{1-v_i{x}^{c_i}})) \\ =\exp (\sum _i(\sum _{j\ge 1}(\frac{1}{j}{x}^{c_{i}j}{v}_i^j)) \\ =\exp (\sum _k\sum _{j\ge 1}\frac{1}{j}{x}^{kj}\sum _{c_i=k}{v}_i^j) \end{gathered}$$
  后面用等幂和算，前面用调和级数预处理
  下面考虑求
  $$\begin{gathered} \sum _k[x^k]f^k=[x^m]f^m\sum _k(\frac{x}{f}{)}^{m-k} \\ [x^m]f^m\frac{1-(\frac{x}{f}{)}^{m+1}}{1-(\frac{x}{f})} \end{gathered}$$
  容易发现 $\frac{x}{f}$ 没有常数项，对 $[x^m]$ 没有贡献，$Code$

Naiive - By FSY
签到题，大家都切掉了，Sol

送分题 - By 大神 ldx

• 考虑随便点 $ti{m}_i$ 个的意义就是 $[x^{ti{m}_i}]\prod e^{a_{i}x}=(\sum a_i{)}^{ti{m}_i}$
  对每个数统计 $gcd$ 是它的倍数的情况容斥回去即可，直接 $n\log n$ 的调和级数过不去，考虑这么一个过程，我们需要将 $\prod p_i^{k_i}$ 不重不漏地加到 $\prod p_i^{k_i+t_i}$，$t_i\ge 0$ 上，那么我们每个质因子做一遍，复杂度 $55\ast n\log n\log n$

构造题 - By 大神zxy

• 首先有限域的大小一定是 $p^k$
  考虑如何构造逆元，我们生成一个最高次数为 1，系数在 $[0,p)$ 之间的不可约的多项式，显然一个多项式对应着一个数，将乘法定义为与其取模，我们暴力枚举两个多项式相乘将它们相乘的结果 $ban$ 掉就可以找出这个合法的多项式，$Code$

这篇关于【互测】20/05/27的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---