2020-2021:teams:wangzai_milk:weekly5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly5 [2020/06/07 19:44] wzx27 |
2020-2021:teams:wangzai_milk:weekly5 [2020/07/01 13:00] (当前版本) zars19 [Zars19] |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| $$f(x)\cdot (\sum x^{i})^{m_1} \cdot (\sum x^{2i})^{m_2} \cdot (\sum x^{3i})^{m_3}$$ | $$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 {n+i-1 \choose i}x^{ik}$ | + | 其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$ |
| 另外模数刚好是998244353，做三次NTT即可 | 另外模数刚好是998244353，做三次NTT即可 | ||
| 行 102: | 行 102: | ||
| ==== 2.整数分拆 ==== | ==== 2.整数分拆 ==== | ||
| - | 生成函数的基本应用，求 $x1+x2+x3\cdots x^k=n$ 的非负整数解得个数。 | + | |
| + | 生成函数的基本应用，求 $x1+x2+x3\cdots x^k=n$ 的非负整数解的个数。 | ||
| === 2.1 有序分拆 === | === 2.1 有序分拆 === | ||
| 把每个数写成生成函数 $(1+x+x^2+\cdots)$ 的形式 | 把每个数写成生成函数 $(1+x+x^2+\cdots)$ 的形式 | ||
| - | 那么分拆数就等于 $(1+x+x^2+\cdots)^k$ 的 $n$ 次项前面的系数$\{n+k-1 choose k-1}$ | + | |
| + | 那么分拆数就等于 $(1+x+x^2+\cdots)^k$ 的 $n$ 次项前面的系数${n+k-1 \choose k-1}$ | ||
| 这个证明可以通过$(1+x+x^2+\cdots)^k=\frac 1{(1-x)^k}$的逐项求导证明 | 这个证明可以通过$(1+x+x^2+\cdots)^k=\frac 1{(1-x)^k}$的逐项求导证明 | ||
| === 2.2 无序分拆 === | === 2.2 无序分拆 === | ||
| 无序的分拆容易想到朴素 $O(n^2)$ 的$\text{dp}$ | 无序的分拆容易想到朴素 $O(n^2)$ 的$\text{dp}$ | ||
| + | |||
| 记 $P(n)$ 为 $n$ 的无序拆分数如果用生成函数来做就是 | 记 $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=1}^\infty=\prod_{i=0}^\infty \frac 1{1-x^i}$$ | + | |
| - | 结合五边形数定理 $\pord_{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})}$ 得到： | + | $$\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$$ | $$(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)-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))$ | 这样就得到了 $P(n)=\sum_{i=1}(-1)^i(P(n-\frac {i(3i-1)}2)+P(n-\frac {i(3i+1)}2))$ | ||
| 行 174: | 行 184: | ||
| [[http://acm.hdu.edu.cn/showproblem.php?pid=4658|HDU4658]] | [[http://acm.hdu.edu.cn/showproblem.php?pid=4658|HDU4658]] | ||
| + | |||
| 拆分时每个数的使用次数要小于 $k$。 | 拆分时每个数的使用次数要小于 $k$。 | ||
| + | |||
| 把生成函数改一下： | 把生成函数改一下： | ||
| - | $$\sum_{i=0}^\infty P(n)x^i=(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{1-x^{ik}}$$ | + | |
| + | $$(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$$ | ||
| <hidden> | <hidden> | ||
| 行 251: | 行 264: | ||
| 不好意思摸了摸了，我马上补555 | 不好意思摸了摸了，我马上补555 | ||
| + | |||
| + | 楼上上好强… | ||
| + | |||
| + | ==== 比赛 ==== | ||
| + | |||
| + | [[Educational Codeforces Round 83 (Rated for Div. 2)]] | ||
| + | |||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
2020-2021/teams/wangzai_milk/weekly5.1591530245.txt.gz · 最后更改: 2020/06/07 19:44 由 wzx27
