2020-2021:teams:alchemist:weekly_digest_10
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_10 [2020/08/14 16:55] maxdumbledore |
2020-2021:teams:alchemist:weekly_digest_10 [2020/08/14 22:11] (当前版本) maxdumbledore |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | 百度之星一场 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | 暂无 | ||
| ===== MountVoom ===== | ===== MountVoom ===== | ||
| 行 41: | 行 47: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | 补题+整理板子 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| 行 66: | 行 73: | ||
| 问题首先转化为所有子集的贡献和。 | 问题首先转化为所有子集的贡献和。 | ||
| - | 将区间交的平方，看作是区间交里面元素两两配对的个数，进一步，是左点。那么问题就是每一对元素，要求出其被区间交覆盖的总次数。我们将所有区间按左端点从小到大排序，按顺序加入区间$i$，这样我们看每个离散化后的原子区间，被区间覆盖的次数，就是左到右不递增了。那么必包含区间$i$时，每个原子区间的每个配对右点在区间交中带来的贡献数的和，就是$（原子区间长度乘以左边的点的个数的和的两倍，再加上原子区间长度平方）\times（2^{覆盖数}-1）$。 | + | 将区间交的平方，看作是区间交里面元素两两配对的个数，进一步，是左点。那么问题就是每一对元素，要求出其被区间交覆盖的总次数。我们将所有区间按左端点从小到大排序，按顺序加入区间$i$，这样我们看每个离散化后的原子区间，被区间覆盖的次数，就是左到右不递增了。那么必包含区间$i$时，每个原子区间的每个配对右点在区间交中带来的贡献数的和，就是$（原子区间长度乘以左边的点的个数的和的两倍+原子区间长度平方）\times（2^{覆盖数}-1）$。 |
| 这些信息，包括次数和乘积等，可以用线段树加以维护，每一次区间更新，然后区间查询即可。 | 这些信息，包括次数和乘积等，可以用线段树加以维护，每一次区间更新，然后区间查询即可。 | ||
| 行 82: | 行 89: | ||
| - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ | - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ | ||
| - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (j<L[i] \lor j>R[i])$ | - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (j<L[i] \lor j>R[i])$ | ||
| - | - $dp[i][j][0/1]=dp[i-1][j][0/1]*2+(j-L[i]^2)\ (L[i]\le j<R[i])$ | + | - $dp[i][j][0]=dp[i-1][j][0]\times 2+(j-L[i])^2,dp[i][j][1]=dp[i-1][j][1]\times 2\ (L[i]\le j<R[i])$ |
| - | - $dp[i][R[i]][0]=dp[i-1][R[i]][0]$ | + | - $dp[i][R[i]][0]=dp[i-1][R[i]][0],dp[i][R[i]][1]=dp[i-1][R[i]][0]+dp[i-1][R[i]][1]\times 2+(R[i]-L[i])^2$ |
| - | - $dp[i][R[i]][1]=dp[i-1][R[i]][0]+dp[i-1][R[i]][1]*2+(R[i]-L[i])^2$ | + | |
| 最后使用线段树或其他数据结构就可以将该$dp$优化到$O(n\log n)$ | 最后使用线段树或其他数据结构就可以将该$dp$优化到$O(n\log n)$ | ||
| 行 97: | 行 103: | ||
| === 来源： === | === 来源： === | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6390|HDU 6390]] | ||
| === 标签： === | === 标签： === | ||
| + | |||
| + | 莫比乌斯反演 | ||
| === 题意： === | === 题意： === | ||
| + | $G_u(a,b)=\frac{\varphi{ab}}{\varphi{a}\varphi{b}}$ | ||
| + | |||
| + | 求解$\sum_{i=1}^{n}\sum_{j=1}^{m}G_u(i,j)$ | ||
| === 题解： === | === 题解： === | ||
| - | === 评论： === | + | $gcd(a,b)=d,\varphi(ab)=\varphi(a)\varphi(b)\frac{d}{\varphi(d)}$ |
| + | |||
| + | $G_u(a,b)=\frac{gcd(a,b)}{\varphi(gcd(a,b))}$ | ||
| + | |||
| + | $ans=\sum_{d}\frac{d}{\varphi(d)}\sum_{a,b}[gcd(a,b)==d]$，可以看出是经典莫比乌斯反演问题 | ||
| + | |||
| + | 时间比较紧，需要线性预处理$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]$，可以整除分块进一步优化 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
2020-2021/teams/alchemist/weekly_digest_10.1597395328.txt.gz · 最后更改: 2020/08/14 16:55 由 maxdumbledore
