constexpr_ll

摘要： 手刃一道黑的蒟蒻太高兴了！！！ 题目传送门 给定三个整数 \(n,m,p\)，求 \[\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(ij,ik,jk)\cdot \gcd(i,j,k)\cdot \left(\frac{\gcd(i,j)}{\gcd(i,k)\c 阅读全文

摘要： 个人感觉这个题还是出得很好的，毕竟他在 IOI2021 国家集训队作业里。 题目给了一个类似递推的式子，还给了矩阵的第一列 \(l_i\) 和第一行 \(t_i\)，求 \(F{n,n}\)。 我们注意到 \(l_i\) 和 \(t_i\) 都是会被重复计算的。 所以我们计算其对于此矩阵的贡献（对于 阅读全文

摘要： 杜教筛 我们之前通过线性筛（欧拉筛）求出了 \(\mu(i)\) 和 \(\varphi(i)\) 的前缀和，以优秀的 \(O(n)\) 抢占先机。 但是，我们在 \(O(nq)\) 的时间复杂度下百万量级的数据是过不了的。 你不要跟我说 WC2026 的文艺汇演说 我们的每一档部分分都是意料之外的 阅读全文

摘要： 题目传送门 我们要求 \[\sum_{i=1}^n \sum_{j=1}^m [i \ne j] \cdot (n \bmod i) \cdot (m \bmod j) \bmod 19940417 \]注意到 \[a \bmod b=a-b\lfloor \frac ab \rfloor \]原式 阅读全文

摘要： 题目传送门 我们要求 \[\sum_{k=l}^r d(k) \bmod 998244353 \]的值。 我们记 \[S(n)=\sum_{k=1}^n d(k) \]则 \[\sum_{k=l}^r d(k)=S(r)-S(l-1) \]而 \[S(n)=\sum_{k=1}^n \lfloor 阅读全文

摘要： 题目传送门 给定 \(n,m\)，求 \[\sum_{i=1}^n \sum_{j=1}^m d(ij) \]的值。 而 \[d(ij)=\sum_{s \mid i} \sum_{t \mid j} [\gcd(s,t)=1] \]则 \[\begin{align*} \sum_{i=1}^n \ 阅读全文

摘要： 突然发现自己做题计划里有这道题，就顺便学了一下莫比乌斯反演。 算法详解 莫比乌斯函数 其核心就是莫比乌斯函数 \(\mu(n)\)，定义在 \(\Z^+\) 上，取值规则为： 当 \(n=1\) 时，\(\mu(n)=1\) 当 \(n \ne 1\) 时 若存在一个质数 \(p\)，使得 \(p^ 阅读全文

摘要： 赛时在最后仅剩不到 \(20\) 秒时发现我 \(m\) 和 \(k\) 输入反了，然后就过了。 作为第一次同时场切 D 和 E 的蒟蒻，决定发一篇题解纪念一下。 题目就是给了一个很长的 \(n\) 和 \(m\)，求 \[\left \lfloor \frac nm \right \rfloor 阅读全文

摘要： 省流：又又又又是毒瘤数据结构。 题目传送门 看到操作一我们想到线段树/树状数组，看到操作二我们想到文艺平衡树。 再结合后面的所有操作，这题就是文艺平衡树裸题。 我们需要维护两个 lazy tag，一个翻转标记，一个加法标记即可。 下面给出二十几行的 pushdown ： void pushdown( 阅读全文

摘要： 省流：又是贪心。。 题目传送门 经典。。 题目大意 平面上给出了 \(n\) 个点，第 \(i\) 个点的坐标为 \((x_i,y_i)\)，现在要求从其中选择三个点组成一个三角形，使得三角形有一条边与 \(x\) 轴平行，还有一条边与 \(y\) 轴平行，求所有满足条件的三角形面积的两倍之和，并对 阅读全文