2020-2021:teams:alchemist:weekly_digest_2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_2 [2020/05/15 11:54] maxdumbledore [陈铭煊 Max.D.] |
2020-2021:teams:alchemist:weekly_digest_2 [2020/05/19 16:24] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 本周是比较摸的一周，主要学习了一下广义后缀自动机（不敢说自己已经会了），稍微写了下FWT的知识库。 | 本周是比较摸的一周，主要学习了一下广义后缀自动机（不敢说自己已经会了），稍微写了下FWT的知识库。 | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | |||
| + | 摸鱼ing | ||
| + | |||
| + | 学习了递推容斥系数计算,学习了三次剩余(非BSGS) | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| + | 这周是特别摸的一周，补了补题，没学啥新东西。 | ||
| + | |||
| + | 摸了一套[[https://codeforces.com/contest/1352|div.4]]和一套[[https://codeforces.com/contest/1353|div.3]]，等明天再摸一套[[http://codeforces.com/contest/1354|div.2]]。 | ||
| + | |||
| + | 爬去写作业了。 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ===== 陈铭煊 Max.D. ===== | ===== 陈铭煊 Max.D. ===== | ||
| 行 30: | 行 39: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | |||
| + | $平面图边数至多为3|V|-6(V+F-E=2,F至多2|V|-4)$ | ||
| + | |||
| + | **含递推关系的期望问题** | ||
| + | |||
| + | $对递推\sum_{i=0}^{n} a_{i}f_{m-i}=0,(a_{0}一般为0以求解f_{m})\\ | ||
| + | 递推的特征多项式为\sum_{i=0}^{n}a_{i}x^{n-i}=0,联接多项式为\sum_{i=0}^{n}a_{i}x^{i}=0$ | ||
| + | |||
| + | $P(x)=\sum_{i=0}^{\infty} p_{i}x^{i},p_{i}为概率i,p_{i}具有线性递推关系,那么期望即P^{'}(1)$ | ||
| + | |||
| + | $考虑H(x)=P(x)G(x),G(x)为递推的联接多项式,后|G(x)|项都应为0$ | ||
| + | |||
| + | $P^{'}(1)=\frac{H^{'}(1)G(1)-H(1)G^{'}(1)}{G(1)^{2}}$ | ||
| + | |||
| + | $实际计算时,若P(x)截取2n项,G(x)由BM算法不超过n项,H(x)也应该只截取前2n项$ | ||
| + | |||
| + | [[http://codeforces.com/gym/102268/problem/E|例题]] | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| + | |||
| + | 不知道推荐什么好，就推荐一道[[https://ac.nowcoder.com/acm/contest/5477/H|数据结构题]]吧。 | ||
| + | |||
| + | [[http://112.74.186.118/doku.php?id=2020-2021:teams:alchemist:mountvoom:training1|题解]] | ||
2020-2021/teams/alchemist/weekly_digest_2.1589514875.txt.gz · 最后更改: 2020/05/15 11:54 由 maxdumbledore
