文章

喵链 题目喵述 求 $$(\sum_{i=1}^n \sum_{j=1}^nijgcd(i,j)) \% p$$ 题解 杜教筛模板题 原式= $$\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==d]ij$$ 显然有 $$\sum_{d=1}^n d^3 阅读更多…

这篇文章是用来复习莫比乌斯反演，可能对新学不是那么友好。 然而如果你熟练莫比乌斯反演的话这里的杜教筛教程也是可以看看的啦（我就是为了学杜教筛才去复习莫比乌斯反演的毕竟忘得差不多了 QAQ）最近一直在肝这篇文章和 yyb 那篇 blog(后者用掉好几节数学课 (雾 狄利克雷卷积: $$(f*g)(n 阅读更多…

题目分析 首先有一个结论：$gcd(fib(a_i))= fib(gcd(a_i))$，可以尝试使用辗转相减球 gcd 的方法证明一下。（boshi: 可以证，但没必要）然后 $lcm$是个什么玩意呢？对于一个指定的质因数 $p$，假设 $a_i$的质因数 $p$的次数为 $c_i$，则他们的 l 阅读更多…

简直闲得蛋疼 代码自己看我懒得解释 下面提供了俩辣鸡字典生成器，然而我更建议使用专业的字典生成器 C++的密码字典生成器 1（将给定子串组合起来）： #include <bits/stdc++.h> using namespace std; string str[20] = { “123 阅读更多…

树链剖分入门练手题。 然鹅我居然调了一个上午+半个上午！ 最后居然是少写了一个 f 导致 WA 了一片 [滑稽]。 总的来说，树链剖分其实并不是那么的难，只需要两个 dfs+线段树+lca 思想即可 AC。 两遍 dfs 很好理解： const int N=3e4+2; struct Node{ i 阅读更多…

集合计数 题意： 求 $[0,2^n-1]$内中选择任意数量 (不能不选) 的几个不同的数，它们按位与后有 $k$个 $1$的方案数。 分析： 我们首先定义一个比较容易计算的函数，$g[x]$，以及我们需要求的函数 $f[x]$。$f[x]$表示 “恰有 x 个 1 出现在最终的结果中” 的方案数。 阅读更多…

题意（From Luogu）： 题目描述 现有 $N$ 个玩具箱，每个玩具箱里都有一些玩具，这些玩具编号为 $1 \dots M$ ，一种玩具可以在多个玩具箱中出现，但每个玩具箱中每种玩具最多只有一个。 现在求：从这些玩具箱中选出一部分使得每种玩具都有的方法数。由于答案很大很大所以 $\bmod 1 阅读更多…

题目链接 我们不妨考虑倒着做这题 首先我们把屏幕反过来然后把自己吊在天花板上倒着做就行了 最后把所有的双端队列连起来是一个排好序的序列，就是说一个双端队列里的元素一定是连续的，因此我们把所有元素按照大小为第一关键字，出现时间为第二关键字排序 然后就按照排好序的顺序一个一个处理元素，划分成一个一个双端 阅读更多…

题目链接：https://www.mina.moe/BZPRO/JudgeOnline/4424.html 题目大意：给定 n 个点，m 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成 一个二分图。 考场上我看到就懵逼了——虽然我的确知道一个图是二分图的充要条件是没有奇环，但是我没有想 阅读更多…

传送门喵呜 一道博弈论好题啊！（其实应该说是一道分块好题 (雾 容易想到每次操作答案就是所有子游戏的 nim 和 考虑如何计算 sg 值 $sg[i]$表示 $i$个石子的 sg 值。 我们有 $$sg[i]=mex\{sg[i/j]\oplus \cdots \oplus sg[i/j] 阅读更多…