2020-2021:teams:legal_string:jxm2001:lgv引理
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:lgv引理 [2021/08/15 14:54] jxm2001 |
2020-2021:teams:legal_string:jxm2001:lgv引理 [2021/08/15 16:02] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 43: | 行 43: | ||
| ===== 算法模板 ===== | ===== 算法模板 ===== | ||
| + | |||
| + | [[https://acm.hdu.edu.cn/showproblem.php?pid=5852|HDU5852]] | ||
| 给定一个二维平面，求满足如下条件的 $k$ 元路径组个数： | 给定一个二维平面，求满足如下条件的 $k$ 元路径组个数： | ||
| 行 120: | 行 122: | ||
| ===== 算法例题 ===== | ===== 算法例题 ===== | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/11260/C|2021牛客暑期多校训练营9 C]] | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| 行 189: | 行 193: | ||
| 具体的，可以设 $f(x)=\sum_{i=1}^n x^{a_i},g(x)=\sum_{i=1}^n x^{-a_i}$，则每个值 $k$ 出现次数就是 $[x^k]f(x)g(x)$。 | 具体的，可以设 $f(x)=\sum_{i=1}^n x^{a_i},g(x)=\sum_{i=1}^n x^{-a_i}$，则每个值 $k$ 出现次数就是 $[x^k]f(x)g(x)$。 | ||
| - | 注意还有 $i\lt j$ 的限制，根据对称性，考虑 $$然后做快速幂即可，时间复杂度 $O(V\log V)$。 | + | 注意还有 $i\lt j$ 的限制，根据对称性，考只考虑 $k\gt 0$ 的部分贡献然后做快速幂即可，时间复杂度 $O(V\log V)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/lgv引理.1629010464.txt.gz · 最后更改: 2021/08/15 14:54 由 jxm2001
