康托展开：现在给你一个长度为排列，求这个排列在长度为的所有排列中 是第几个排列(即求其排名)。   假设现在的排列是   那么排名等于，其中表示在剩余数组里面有多少个比小的数的个数   例如排列      时，剩余数组为，里面有个数比小，所以    时，剩余数组为    ，里面有个数比小，所以   时，剩余数组为         ，里面有个数比小，所以   时，剩余数组为             ，里面有个数比小，所以  时，剩余数组为&nbsp...

两种求解逆元的方法：快速幂和扩展欧几里得算法，时间复杂度都为，是模数      这道题目需要求从到所有数对的乘法逆元，时间复杂度为，最坏情况是，给卡超时了   正确的解法是线性逆元，在的时间复杂度求出从到所有数对的乘法逆元，该方法是线性从前推后，所以与时间复杂度与没有关系      现在如何求?   设   ，两边同时乘以，则   即，化简为   所以   因为，   所以，因为为负数，所以   总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #defin...

我觉得这道题目十分考验码力      例如现在的位置是，根据题意，假设下一步可以到达的点是，每一个点满足   那么   我们有结构体存每个位置的   struct Node{     int x, y, sum; }; 显然需要将从小到大排序，这样从小到大处理，直接就可以很快找到这个值   处理第个位置时，   int total_cnt = 0; for(int j = 1; j < i; j ++...

一个拥有个面的骰子，期望投掷多少次才能保证每一面都至少出现过一次？   设随机变量表示上述条件所需的投掷次数，求      设：   表示：现在已经有个面了，还需要期望投掷次会有个面   表示：现在已经有个面了，还需要期望投掷次会有个面   表示：现在已经有个面了，还需要期望投掷次会有个面   ...   表示：现在已经有个面了，还需要期望投掷次会有个面   那么   即转化为求了：   现在已经有个面了，还需要期望投掷次会有个面   那么直接投掷出还没有出现的面的概率为，投掷出已经出现过的面的概率为   几何分布：几何分布是离散型机率分布。描述第次伯努利试验成功的机率。详细的说，是： 次伯努...

给定一个有向无环图，个点，条边，可以存在重边。设为图中所有简单路径(允许长度为，即起点与终点相同)的集合。   从集合中等概率随机选择一条路径并沿着它行走，定义一条路径的长度为其经过的边数   即随机变量为所选路径的长度，计算的期望值对取模的结果，即    显然是离散型随机变量：的取值可以为，设对应的路径条数为   那么   所以现在就是求每个长度的路径的条数：   因为每个点都可以作为起点，如果从每个点一遍的话，时间复杂度为，一定超时的！   所以用到了拓扑排序+的方法：   定义表示以节点为终点的全部路径条数;当时，   定义表示以节点为终点的全部路径的长度；当时，   详细解释：    ...

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