2020-2021:teams:alchemist:weekly_digest_11
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 16:22] hardict [比赛] |
2020-2021:teams:alchemist:weekly_digest_11 [2020/08/21 17:24] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 35: | 行 35: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 求求来点正常cf div1 | + | 打了atcoder，rating小涨。 |
| - | + | ||
| - | 遇见类似原题的题不要被轻易影响 | + | |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 50: | 行 48: | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| - | 该补点难题了 | + | 补题，学点新东西 |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 88: | 行 86: | ||
| === 来源： === | === 来源： === | ||
| - | [[http://acm.hdu.edu.cn/showproblem.php?pid=6390|HDU 6390]] | + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6061|HDU 6061]] |
| === 标签： === | === 标签： === | ||
| - | 莫比乌斯反演 | + | 多项式卷积,NTT |
| === 题意： === | === 题意： === | ||
| - | $G_u(a,b)=\frac{\varphi{ab}}{\varphi{a}\varphi{b}}$ | + | 先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$ |
| - | 求解$\sum_{i=1}^{n}\sum_{j=1}^{m}G_u(i,j)$ | + | 输出$b_{i}$ |
| === 题解： === | === 题解： === | ||
| - | $gcd(a,b)=d,\varphi(ab)=\varphi(a)\varphi(b)\frac{d}{\varphi(d)}$ | + | $A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算 |
| + | |||
| + | 然后按$f(x+A)$每一项进行一个展开(会成一个三角表) | ||
| + | |||
| + | 目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$ | ||
| + | |||
| + | 化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$ | ||
| + | |||
| + | 整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$ | ||
| - | $G_u(a,b)=\frac{gcd(a,b)}{\varphi(gcd(a,b))}$ | + | 这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} |
| + | =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$ | ||
| - | $ans=\sum_{d}\frac{d}{\varphi(d)}\sum_{a,b}[gcd(a,b)==d]$，可以看出是经典莫比乌斯反演问题 | + | 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 |
| - | 时间比较紧，需要线性预处理$1\sim n$逆元，进一步$\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)==d]=\sum_{i=1}^\frac{n}{d}\sum_{j=1}^\frac{m}{d}[gcd(i,j)==1]$，可以整除分块进一步优化 | ||
| 行 115: | 行 121: | ||
| === 来源： === | === 来源： === | ||
| - | [[https://ac.nowcoder.com/acm/contest/5675/J|牛客第十场 J. Identical Trees]] | + | [[https://atcoder.jp/contests/abc175/tasks/abc175_d|D - Moving Piece]] |
| === 标签： === | === 标签： === | ||
| - | 树形dp，二分图最大权匹配，树哈希 | + | 枚举，贪心 |
| === 题意： === | === 题意： === | ||
| - | 给定两棵同构的树，需要找到一个对应关系使得相同的标号尽可能多。 | + | 给定步数和诸多环，求在某个环上走的最大收益。 |
| === 题解： === | === 题解： === | ||
| - | 树形dp，dp[i][j]表示把第一棵树的i结点和第2棵树的j节点对应起来所需要的最小花费。 | + | 枚举每个点作为起点然后分类讨论，如果步数不够一圈就模拟一下找一个最大值。 |
| - | 转移的时候对它们的子树做一个二分图最大权匹配即可，这样总的复杂度仍然是$O(n^3)$ | + | 如果够一圈则在模拟走一圈内的最大值和走多圈和余下步数的最大值取个最大值即可。 |
| === 评论： === | === 评论： === | ||
| - | cmx鸽鸽写的时候树哈希被卡了，需要注意 | + | 分类没有处理好WA了很多发，这种简单题也要注意细节。 |
2020-2021/teams/alchemist/weekly_digest_11.1597998174.txt.gz · 最后更改: 2020/08/21 16:22 由 hardict
