2020.06.01-2020.06.07 周报
团队训练
本周暂无
_wzx27
1.补题
补了一下之前比赛的题
把数列 $a_i$ 写成其生成函数的形式 $f(x)=\sum a_ix^i$，每个操作 $k$ 相当于 $f(x)\cdot \sum x^{ik}$，由交换律知顺序不重要，所以可以统计每种操作的次数 $m_i$，最后有
$$f(x)\cdot (\sum x^{i})^{m_1} \cdot (\sum x^{2i})^{m_2} \cdot (\sum x^{3i})^{m_3}$$
其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$
另外模数刚好是998244353，做三次NTT即可
2.整数分拆
生成函数的基本应用，求 $x1+x2+x3\cdots x^k=n$ 的非负整数解的个数。
2.1 有序分拆
把每个数写成生成函数 $(1+x+x^2+\cdots)$ 的形式
那么分拆数就等于 $(1+x+x^2+\cdots)^k$ 的 $n$ 次项前面的系数${n+k-1 \choose k-1}$
这个证明可以通过$(1+x+x^2+\cdots)^k=\frac 1{(1-x)^k}$的逐项求导证明
2.2 无序分拆
无序的分拆容易想到朴素 $O(n^2)$ 的$\text{dp}$
记 $P(n)$ 为 $n$ 的无序拆分数如果用生成函数来做就是
$$\sum_{i=1}^\infty P(i)x^i=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots=\prod_{i=0}^\infty \frac 1{1-x^i}$$
结合五边形数定理 $\prod_{i=0}^\infty (1-x^i)=1+\sum_{i=1}^\infty (-1)^i(x^{\frac {i(3i-1)}2}+x^{\frac {i(3i+1)}2})$ 得到：
$$(1+P(1)x+P(2)x^2+\cdots)(1-x-x^2+x^5+\cdots)=1$$
比较两边的系数得到 $P(n)-P(n-1)-P(n-2)+P(n-5)=0$，即$P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)-\cdots = 0$
这样就得到了 $P(n)=\sum_{i=1}(-1)^i(P(n-\frac {i(3i-1)}2)+P(n-\frac {i(3i+1)}2))$
HDU4651 模板题
拆分时每个数的使用次数要小于 $k$。
把生成函数改一下：
$$(1+x+x^2+\cdots+x^{k-1})(1+x^2+x^4+\cdots+x^{2(k-1)})\cdots=\prod_{i=1}^\infty \frac {1-x^{ik}}{1-x^i}=\phi(x^k)\sum_{i=0}^\infty P(n)x^i$$
Infinity37
在搞期末考试，完全摸了
Zars19
不好意思摸了摸了，我马上补555
楼上上好强…
