2020-2021:teams:legal_string:组队训练比赛记录:contest13
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest13 [2021/08/15 11:15] 王智彪 |
2020-2021:teams:legal_string:组队训练比赛记录:contest13 [2021/08/15 11:40] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| | F | 2 | 0 | 1 | | | F | 2 | 0 | 1 | | ||
| | G | 0 | 0 | 0 | | | G | 0 | 0 | 0 | | ||
| - | | H | 0 | 0 | 2 | | + | | H | 1 | 0 | 2 | |
| | I | 0 | 0 | 0 | | | I | 0 | 0 | 0 | | ||
| | J | 2 | 1 | 0 | | | J | 2 | 1 | 0 | | ||
| 行 128: | 行 128: | ||
| </hidden> | </hidden> | ||
| - | ====== H.Scholomance Academy ====== | + | ===== H.Scholomance Academy ===== |
| 注意到 $F(n)$ 是一个积性函数，因为对于两堆不同的质因子放进去，因为欧拉函数是积性函数，我都可以分成两堆，一堆装第一类，一堆装第二类，然后发现和单独相乘是一一对应的关系，必然相等。 | 注意到 $F(n)$ 是一个积性函数，因为对于两堆不同的质因子放进去，因为欧拉函数是积性函数，我都可以分成两堆，一堆装第一类，一堆装第二类，然后发现和单独相乘是一一对应的关系，必然相等。 | ||
| 行 134: | 行 134: | ||
| 于是我们单独对每个质因子拆开计算。 | 于是我们单独对每个质因子拆开计算。 | ||
| - | 我们考虑生成函数 $G_{p}(x)=F(p^{0})+F(p^{1})+...$ ，然后所有质因子的生成函数乘起来的 $n$ 次项就是 $G(N)$ 的结果了。 | + | 我们考虑生成函数 $G_{p}(x)=F(p^{0})+F(p^{1})x^{1}+...$ ，然后所有质因子的生成函数乘起来的 $N$ 次项就是 $G(N)$ 的结果了。 |
| - | 这东西等于 $(\phi (p^{0})+\phi (p^{1})+...)^{m}$ | + | 这东西等于 $(\phi (p^{0})+\phi (p^{1})x^{1}+...)^{m}$ |
| 化简得到 $(\frac {1-x} {1-px})^{m}$ ，然后所有的质因子乘起来，最后分子分母都是最高次项为 $mt$ 次方的多项式，设除的结果为 $h(x)$ ，我们要求 $h(x)$ 的第 $n$ 次项，设分子为 $f(x)$ ，分母为 $g(x)$ 。 | 化简得到 $(\frac {1-x} {1-px})^{m}$ ，然后所有的质因子乘起来，最后分子分母都是最高次项为 $mt$ 次方的多项式，设除的结果为 $h(x)$ ，我们要求 $h(x)$ 的第 $n$ 次项，设分子为 $f(x)$ ，分母为 $g(x)$ 。 | ||
| - | 然后这东西是可以常系数齐次线性递推搞的：对于高于 $mt$ 次的系数，$[x^{n}]f(x)$ 必然是 $0$ ，然后有： [x^{n}]f(x)=0=$\sum_{i=0}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，然后我们就有 $[x^{n}]h(x)×[x^{0}]g(x)=-\sum_{i=1}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，这玩意求逆元化简之后，就变成了一个常系数齐次线性递推的板子。 | + | 然后这东西是可以常系数齐次线性递推搞的：对于高于 $mt$ 次的系数，$[x^{n}]f(x)$ 必然是 $0$ ，然后有： $[x^{n}]f(x)=0=\sum_{i=0}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，然后我们就有 $[x^{n}]h(x)×[x^{0}]g(x)=-\sum_{i=1}^{mt}[x^{n-i}]h(x)×[x^{i}]g(x)$ ，这玩意求逆元化简之后，就变成了一个常系数齐次线性递推的板子。 |
| - | 这里有两个需要注意的地方， $n$ 比较小的时候，是要直接输出多项式逆元乘法的第 $n$ 项，然后递推的时候递推的系数是 $[x^{1}]g(x)$ 到 $[x^{mt}]g(x)$ 然后因为 $[x^{mt}]f(x)≠0$ ，所以这个 $n$ 要从 $mt+1$ 开始取，也就是说要我们初始项是 $[x^{1}]h(x)$ 到 $[x^{mt}]h(x)$ 然后就需要向前挪一项，然后求 $n-1$ 次的系数。 | + | 这里有两个需要注意的地方， $n$ 比较小的时候，是要直接输出多项式逆元乘法的第 $N$ 项，然后递推的时候递推的系数是 $[x^{1}]g(x)$ 到 $[x^{mt}]g(x)$ 然后因为 $[x^{mt}]f(x)≠0$ ，所以这个 $N$ 要从 $mt+1$ 开始取，也就是说要我们初始项是 $[x^{1}]h(x)$ 到 $[x^{mt}]h(x)$ 然后就需要向前挪一项，然后求 $N-1$ 次的系数。 |
| <hidden 代码> | <hidden 代码> | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest13.1628997333.txt.gz · 最后更改: 2021/08/15 11:15 由 王智彪
