「CF102354」Yet Another Convolution
题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$...
题目链接题目大意有两个长度为 $n$ 的序列序列 $a$ 和 $b$，要求你计算出一个长度为 $n$ 的序列满足我们令 $sm_d = \sum_{d|j} [b_j \geq b']$。发现 $sm$ 只会根据 $b'$ 的变化而变化 于是我们想到了整体二分。整体二分的时候运用类似于莫队的移动指针的技巧 预处理因数分解和 $\mu$ 就可以快速判定了。时间复杂度 $O(nlog^3n)$...
题目大意给长度为 $n$ 的序列，询问有多少个子序列满足它们的 gcd 为 $1$。题解其实这篇博客是用来 水 的 （强行刷文章量） 我们设 $f(x)$ 表示 $gcd = x$ 的子序列的数量，那么可以立马启发我们设 $F(x)$ 表示 gcd 是 $x$ 的倍数的子序列数量，如果我们统计出 $cnt_i$ 表示 $i$ 和 $i$ 的倍数的数量，那么 $F(x) = 2^{cnt_x}...
UPD：狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。积性函数定义对于一个函数 $f$，若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$，则我们称这样的函数为积性函数。 举例：$\phi(x),\mu(i),d_k(n)$（$n$ 的所有正因子 $k$ 次幂和）性质若 $f(x)$ 为积性函数。 设 $n = \Pi p_i^{q_i}$，则...