2020-2021:teams:wangzai_milk:weekly6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly6 [2020/06/09 22:32] wzx27 |
2020-2021:teams:wangzai_milk:weekly6 [2020/07/01 13:03] (当前版本) zars19 [Zars19] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020.06.01-2020.06.07 周报 ====== | + | ====== 2020.06.08-2020.06.14 周报 ====== |
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| + | 2020.06.14 [[https://codeforces.com/gym/101611|2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest]] ''prob:6:6:10'' ''rnk:124/?'' | ||
| + | [[20200614比赛记录]] | ||
| ===== _wzx27 ===== | ===== _wzx27 ===== | ||
| 行 92: | 行 94: | ||
| === 2.生成函数与多项式 === | === 2.生成函数与多项式 === | ||
| - | 有时候生成函数没那么好求的时候就要用多想是全家桶 | + | 生成函数没那么好求的时候就要用多项式全家桶 |
| [[https://www.luogu.com.cn/problem/P4389|P4389付公主的背包]] | [[https://www.luogu.com.cn/problem/P4389|P4389付公主的背包]] | ||
| - | $n$ 中物品，每个物品体积为 $v_i$，求恰好装下体积为 $1~m$ 的种数。 | + | $n$ 种无限个物品，每个物品体积为 $v_i$，求恰好装下体积为 $1~m$ 的种数。 |
| 数据范围：$n,m \le 1e5$ | 数据范围：$n,m \le 1e5$ | ||
| 行 108: | 行 110: | ||
| \begin{aligned} | \begin{aligned} | ||
| lnf(x) =&\sum_{i=1}^n\sum_{j=0}^\infty \frac {x^{j\cdot v_i}}j \\ | lnf(x) =&\sum_{i=1}^n\sum_{j=0}^\infty \frac {x^{j\cdot v_i}}j \\ | ||
| - | =&\sum_{k=0}^n \sum _{v_i|k} \frac {v_i}k x^k | + | =&\sum_{k=0}^m \sum _{v_i|k} \frac {v_i}k x^k \pmod{x^{m+1}} |
| \end{aligned} | \end{aligned} | ||
| $$ | $$ | ||
| - | $O(nlogn)$预处理出$k$的所有因子，然后求 $e^{lnf(x)}$ 即可。 | + | $O(nlogn)$预处理出 $k$ 的所有因子，然后多项式 $\text{Exp} $求 $e^{lnf(x)}$ 即可。 |
| <hidden code> | <hidden code> | ||
| <code cpp> | <code cpp> | ||
| 行 239: | 行 241: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </cpp> | + | </code> |
| </hidden> | </hidden> | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| + | [[20200614比赛记录#d_decoding_of_varints|D.Decoding of Varints]] | ||
| + | [[20200614比赛记录#h_hilarious_cooking|H.Hilarious Cooking]] | ||
| ===== Zars19 ===== | ===== Zars19 ===== | ||
| + | ==== 题目 ==== | ||
| + | |||
| + | [[20200614比赛记录#C.Carpet]] | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
2020-2021/teams/wangzai_milk/weekly6.1591713127.txt.gz · 最后更改: 2020/06/09 22:32 由 wzx27
