必须知道期望的公式，知道公式了就直接快速幂解决了      设一个离散型随机变量的所有可能的取值为，这些取值对应的概率为，则，这个叫做离散型随机变量的均值或者数学期望(简称期望)      但题目连续性随机变量，那么   所以第一个人：剩余金额为，获得红包的期望金额为   所以第二个人：剩余金额为，获得红包的期望金额为   所以第三个人：剩余金额为，获得红包的期望金额为   ...   所以第个人：剩余金额为，获得红包的期望金额为   即求      总代码： #include<bits/stdc++.h> using namespace std; #defin...

从原点到点的这一条射线，如果，那么这条射线一定经过并且最先经过点      题目的意思相当于从朝这范围里面发射无数条射线，求每条射线最先经过的点的个数   范围是   当或者时，只有一个点即或者   当时也满足条件   然后显然可以用欧拉函数直接得到，但是欧拉函数求的是有多少个与互质的数，所以结果得先乘以，然后最后加上   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #def...

给定，求   例如时，即求   这与上一道题洛谷P4139 上帝与集合的正确用法十分相似，但是仍有区别   推一下这道题目的欧拉公式吧：   定义   所以求.....   可以写出大致的代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NUL...

定义，可以证明，在某一项后都是同一个值，求这个值                  ....     即求解 2 的无限次幂塔模 p，利用扩展欧拉定理递归简化幂运算，同时通过线性筛（欧拉筛） 预处理欧拉函数值，保证计算效率      ，所以转化为求   同样的：，.....   所以容易看出是个递归问题，可用搜索解决，递归到最后情况是，即，所以返回结果，这也是为什么题目说可以证明在某一项后都是同一个值      因为频繁用到，又是多组测试数据，所以同时通过线性筛（欧拉筛） 预处理欧拉函数值：   const int N = 1e7 +&nbsp...

给定三个正整数，，求，其中    快速幂的时间复杂度为，最大为，；先不说可不可能超时的问题，这个数字得用字符串存储，所以快速幂并不能直接解决。   正确的解法是使用扩展欧几里得定理      欧几里得定理：   如果整数与整数互质，则有，其中是欧拉函数，表示到与互质的数的个数      如果为质数，那么，则有，此时欧拉定理就退化为费马小定理，所以费马小定理是欧拉定理的一个特殊情况。   欧拉定理的最大作用是用来"降幂"，将指数通过欧拉函数缩小，从而简化大指数幂的计算：   对于，若，则可将指数对取模，即   但是欧拉函数有两个明显的限制：     必须满足整数与整数互质   不能处理大指数且整...

对于整数，若存在整数满足：，则称 是在模意义下的乘法逆元，记为   首先，求解乘法逆元的方法有两种：   方法一：费马小定理   使用该方法的前提是：必须是质数，并且与互质(不是的倍数)   费马小定理内容：   如果是质数，那么对任意与互质的整数，有c成立   那么，所以，即可用快速幂方法      方法二：扩展欧几里得   使用该方法的前提是：仅需要与互质   扩展欧几里得用于求解线性不定方程的一组整数解   当与互质，即时，原式变为求解，两边同时对取模，得到，故模的正余数就是的乘法逆元      方法一需要快速幂(已经倒背如流了)，所以详细介绍扩展欧几里得算法：   扩展欧几里得算法是对...

欧拉函数表示中与互质的数的个数   求： 首先将经行质因数分解：，其中是不同的质因子   那么与互质的数不能被整除，从到一共有个数，那么：   第一步：减去能被单个质因子整除的数的个数   能被整除的数有个，能被整除的数有个，...，能被整除的数有个   所以第一步要减去   第二步：加上能被两个质因子整除的数的个数   能被整除的数有个，能被整除的数有个....   所以第二步要加上   第三步：减去能被三个质因子整除的数的个数   第四步：加上能被四个质因子整除的数的个数   .....   直至处理完个质因子   那么   这个复杂的式子有一个非常优美的乘积形式：   ，即   总代码:...

给定长度为的数组，执行两种操作：     求解整个序列的第小的值   将这个位置上的元素修改为，即    每次操作时，输入一个整数，如果，那么执行操作1；如果，则再输入一个整数，然后将的值修改为    传统线段树是维护数组下标区间的信息，例如：   区间和：   区间最大值：    而权值线段树(也称为值域线段树)维护数值的值域区间，例如：   数值在范围里面出现的次数   整个集合中第小的数       在权值线段树中，每一个叶子节点，那么，就是该数字，而表示出现的次数。   所以只需要维护次数即可：   因为每一个节点的就是该数字，一共需要个叶子节点，那么需要开的，其中，也就是说范围是与数...

给定长度为的字符串(下标范围为)，执行两个操作：   区间取反：将这个区间中的全部元素进行取反操作，    区间数一：输出下标在这个区间中的所有元素值为的元素的个数，即    前面有一道简单的题目是相同的区间取操作+单点查询的值为还是，解决的办法是维护区间的取反次数，如果为奇数，那么输出，否则输出   但是这里区间查询这个区间中的的的个数，但是是一模一样的，没有任何区别！   结果就是我以为线段树不能解决，然后想到用分块来做：   分块+二分优化：    #include<bits/stdc++.h> using namespace std; #def...

给定长度为的数组，执行两种操作：     单点修改：将这个位置上的元素修改为，即   区间非平凡异或和查询：输出下标在这个区间的所有连续子数列的异或和的异或和，即    容易发现的规律：例如: 在连续子序列中出现的次数一共为 (左边数字的个数 + 1) (右边数字的个数 + 1)   如果区间的长度为偶数，那么以为例子，那么出现的次数为，那么出现的次数为.....   那么出现的次数是，，.....，因为偶数个相同的数字异或结果为0，那么所以的长度为偶数时，结果直接等于0   如果区间的长度为奇数，那么就是，，，.....交替，即要么是区间所有下标为偶数的值异或，要么是所有下标为奇数...

给定长度为的数组，执行两种操作：     区间增量：将这个区间中的全部元素修改为其与一个数相加后的值，即    区间小于计数：输出下标在这个区间中的所有元素中小于一个特定的数的元素的个数，即    如果用线段树来做，是维护区间的最大值和区间的和：   操作一：就是基本操作维护区间累加   操作二：使用优化查询的区间个数，如果一个区间的比小，那么直接返回，否则继续寻找子节点   但是在很坏的情况下，操作二查询区间时，总是大于等于，那么最坏会遍历所有的叶子节点，时间复杂度从退化为，导致超时   线段树的代码(一共30个测试数据，通过了29个，最后1个超时了)   #include<...

给定长度为的数组，执行三种操作：     区间加数：将这个区间中的全部元素修改为其与一个数相加后的值，即   区间乘数：将这个区间中的全部元素修改为其与一个数相乘后的值，即    单点求值：输出下标为的元素的值对取模后的结果，即    基础的版本是区间加数，使用的方法是用懒标记来传递，那么区间乘数也是需要一个懒标记的。   需要思考的是两个懒标记该如何传递，先加后乘与先乘后加是不一样的   解决的方法是将先加后乘转化为先乘后加：先加上再乘以等于，转化为先乘以再加上   所以当执行操作时，也需要乘以   部分代码：   void modify_mul(int u,&...

给定，以及数组的递推式：   定义，的意思是能被整除，或者说是的一个因子。   例如，，，......    const int N = 2e6 + 10; int n, a_begin, m; int a[N], b[N]; signed main(){     HelloWorld;          cin >> n&n...

给定长度为的数组，执行两种操作：     区间根号：将 这个区间中的全部元素修改为其开根号后的值，即   区间和查询：输出下标在这个区间中的所有元素之和，即    维护区间开根号十分困难，但是仔细想会知道开根号的次数不会超过5次(连续开根号次就变成了，即使是级别，连续开根号次就变成了)   所以需要维护区间的最大值，如果这个区间的最大值是，那么这个区间就不需要再执行操作了，直接跳过。如果不为，就直接暴力循环区间将每一个数开根号。最多只会修改次，其中是一个很小的常数。   总代码： #include<bits/stdc++.h> using namespace&n...