19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共137篇）

P3327 [SDOI2015]约数个数和来自专栏

求解：因子和函数的一个特殊的性质，带回原式,有：预处理筛出函数，然后分块处理询问。 code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn...

莫比乌斯函数莫比乌斯反演数论分块因子和函数

2021-09-14

1 491

P6271 [湖北省队互测2014]一个人的数论

为了方便计算，这里用变量名表示题目中的求解：则原式：自然数幂和是一个次多项式，可以用伯努利数算出系数，不妨记为由伯努利公式得：则原式：令，易知是积性函数，令，则有则 Code: #include <bits/stdc++.h> using namespace...

莫比乌斯函数莫比乌斯反演伯努利公式组合数

2021-09-08

1 448

P1829 [国家集训队]Crash的数字表格 / JZPTAB 来自专栏

求值：易得原式如下：枚举最大公因数：非常经典的式子的化法：式子的后半段出现了互质数对之积之和，考率先单独拿出来,记有：观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记可以求解。至此：我们可以数论分块求解这部分。回到定义的地方，则原式为：这...

莫比乌斯函数莫比乌斯反演数论分块

2021-09-05

1 503

LCM Sum 来自专栏

求值：易得原式如下： (通常，我们一般会选择将化成来观察) 将原式复制一份得：考虑到，可以将原式改为：式中为了保证有意义，将值为的一项提取出来。两个求和式中分母相同的项可以合并。即：考虑枚举，所以只需要统计的个数，因为，所以,所以满足这个条件的的数量为。故答案为：到这里...

莫比乌斯函数莫比乌斯反演

2021-09-05

1 581

E. Mocha and Stars 来自专栏

如果求解：根据莫比乌斯的一般套路，很容易想到如下转化：即将原式转化为莫比乌斯函数后交换求和顺序。考虑问题二的限制，有：，这部分就是个背包问题，假设表示前个数相加和为的方案数。那么转移方程有：直接转移复杂度是的，注意到等式右边可以用前缀和维护，令，则有：显然只要先用更新，再...

莫比乌斯函数莫比乌斯反演

2021-09-04

1 521

P2522 [HAOI2011]Problem b 来自专栏

求：根据容斥原理，可以分为四部分来求，每一部分都可以拆成：考虑到可以转化，所以为了化简式子，可以：原式式子出现莫比乌斯函数后，通常可以考虑交换求和顺序，枚举,即：很显然，只要预处理莫比乌斯函数，然后用数论分块求解式子。 Code: #include<bits/stdc++.h...

莫比乌斯反演莫比乌斯函数数论分块

2021-09-04

1 540

Add or Multiply 1

思路：一个算式肯定是加法和乘法交替的。假设乘法被分成个连续的段，加法被分成个连续的段，那么一定有。当时只想到了对每组连续的加法，如果元素不完全相同，那么运算的结果就会不同。正确的想法是：对于每组连续的加法或者乘法，如果组内的元素是相同的，那么运算的结果也是一样的。于是可以考虑将乘法分成或个连续的段...

第二类斯特林数组合数

2021-08-23

1 470

D. Ezzat and Grid 来自专栏

思路线段树优化表示线段能组成漂亮序列最多的行数。那么每次转移的时候，区间上查找与线段对应位有的所有线段，选取最大的一个线段，那么。考虑用线段树去优化，区间上找最大的，然后得到，接着用覆盖线段的区间。因为这个只和上一个状态有关，所以可以直接覆盖。 code: #include<bits/s...

线段树

2021-08-17

2 591

Increasing Subsequence

思路方法一状态方程：状态方程中的表示的是数组的下标，即位置。，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数）；，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数）状态转移方程：表示事件发...

记忆化搜索 dp 期望dp

2021-08-15

1 518

Journey among Railway Stations

思路：考虑如何合并两个相邻的区间，假色表示从出发允许最早的时间，表示从出发允许最晚的时间，表示从到需要的时间。比较和能否和并，其实只需要满足。有没有其它的判断方式呢，有，但是没必要：。（这不是没事找事吗，主要是补题的时候想换个思路写，想通过维护一个和一个来完成合并，画个图就知道这样比较冗余）。所...

线段树

2021-08-11

1 447