范艺杰

分类

题解(20)

/ 注册

全部文章（共20篇）

牛客练习赛84 F 牛客推荐系统开发之下班

好像只有我的公式是长这样的，但是跑的最快。考虑到其中，*是狄利克雷卷积，I是单位1。进行杜教筛即可。这里提一点，一个函数和mu卷是可以O(n)的求的。 #include <cstdio> #include <cstring> #include <algorithm&...

2021-06-11

3 617

牛客练习赛84 E 牛客推荐系统开发之标签重复度

考虑使用点分树维护，每次维护经过点分中心的权值。我们考虑计算每个点到点分中心的最小值和最大值，然后合并两个到点分中心的路径。将这样的最大最小值对按最小值排序后，计算贡献。考虑到后计算到的点最小值一定更大，则只有两种情况。1.最大值比之前的大，则贡献是之前的最小值乘现在的最大值。2.最大值比之前的小，...

2021-06-11

3 601

牛客练习赛81 E 小Q与函数求和1

其中是完全积性函数,可线性筛。其余部分可以处理。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; cons...

2021-04-23

10 696

牛客练习赛81 C 小Q与构造

首先，k=1我们发现没有合法的。其次，对于k>=2的情况，我们可以分成若干链进行求解，链长很短。如果没有q的限制，则很显然记录最后一个选不选就行了。由q的限制，则记录最后q个数选的情况。看起来复杂度是2^q的，但是按照不能相邻来剪枝，状态不超过200个。进行dp即可。 #include <...

2021-04-23

7 633

牛客IOI周赛23-提高组 A-单词

先用kmp求出t能出现在s的哪些位置。我们维护这样的三个dp方程：dp1[i]表示最后一个区间结尾r在i的方案数。dp2[i]表示最后一个区间结尾r在[0...i]的方案数。dp3[i]表示最后一个区间开头l在[0...i]的方案数。转移即可，dp2[n]即为答案。复杂度O(n)。 #incl...

2021-03-07

5 699

牛客2020跨年场 D 衔尾蛇

我们发现题目中有若干旋转置换。而对于一共有n条蛇的环而言，本题对应的置换群由一个单位置换和n-1个旋转置换构成。根据burnside引理我们可以对于每个置换求出不变的颜色数进而求出答案。对于单次确定三种蛇使用个数的情况，即代码中的cal(a, b, c)复杂度是O((a+b+c)log(a+b+c)...

2021-01-01

8 809

牛客挑战赛46 E 反演

考虑使用min25。令f(p^c)是当p为质数时的答案，根据积性函数的性质，可以进行min25筛。但是选择的质数小于等于m时，f(p^c) != c + 1。处理这些奇异值即可进行min25筛。 #include <cstdio> #include <algorithm> #...

2020-12-14

3 739

牛客练习赛73 D 离别

我们发现，对于一个固定的右端点r而言，合法的左端点l一定是一个连续的区间，从某个数第一次出现k次开始合法，到某个数第一次出现k+1次开始不合法。因为我们对询问按右端点离线，对于每扫描一个右端点时将合法的左区间加入到线段树中，然后统计即可O(nlog(n))。 #include <cstdio&...

2020-11-25

4 681

牛客挑战赛44 斐波那契？数列！

第一问：根据线性递推序列的特征方程理论，我们可以根据递推方程构造特征多项式，使用特征多项式的根来构造通项方程。而an^2也可以直接对通项平方，我们发现an^2也是由某个特征多项式的根构成。构造这个特征多项式，进而可以构造出线性递推方程。因此我们可以断言，an^2也是线性递推的。对于线性递推方程，我们...

2020-10-17

3 789

牛客练习赛71 E 神奇的迷宫

题目可以简化为ans[i]表示距离为i的点对个数的概率和，求出这个概率和即可。考虑使用点分支分解整棵树，然后在子树中选取深度小的进行启发式合并，这里合并用ntt进行加速。复杂度O(nlognlogn)。 #include <cstdio> #include <algorithm&g...

2020-10-10

8 675