快速幂，离散化

倍增思想倍增顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理极⼤地优化时间复杂度。1.1P1226 【模板】快速幂解题思路1.暴力for循环得到a^b 但是a和b的范围太大会超时。2.倍增利用二进制把次数用二进制表示只需累乘对应位数大大减少遍历次数当计算过程中只有加法和乘法可以随意位置%(abcd)%e(a%eb%ec%ed%e)%e当计算过程中有减法时结果可能出现负数如果需要补正就需要“模模”来补正(a-b)%p((a-b)%pp)%p代码#includeiostreamusingnamespacestd;typedeflonglongLL;LL a,b,p;LLqpow(LL a,LL b,LL p){LL ret1;while(b){if(b1){retret*a%p;}b1;aa*a%p;}returnret;}intmain(){cinabp;printf(%lld^%lld mod %lld%lld,a,b,p,qpow(a,b,p));return0;}1.2P10446 64位整数乘法解题思路代码#includeiostreamusingnamespacestd;typedeflonglongLL;LL a,b,p;LLqpow(LL a,LL b,LL p){LL ret0;while(b){if(b1){ret(reta)%p;}b1;a(aa)%p;}returnret;}intmain(){cinabp;printf(%lld,qpow(a,b,p));return0;}2.离散化当数据范围大但是数据的数量很小时如果我们要使用数据对应的数组下标我们可以使用离散化。⽤离散化的思想先预处理⼀下所有的数据使得每⼀个数据都映射成⼀个较⼩的值。之后再⽤离散化之后的数去处理问题。⽐如[99, 9, 9999, 999999] 离散之后就变成[2, 1, 3, 4] 。【案例】题⽬描述给定n 个数离散化之后输出每⼀个数离散化之后的值。测试数据101999999121999999-4844456812-100-2845630100000001263// 输出7472643185离散化模板⼀ 排序去重⼆分离散化之后的值#includeiostream#includealgorithmusingnamespacestd;constintN1e510;inta[N];intdist[N];intn;intfind(intkey,intpos){intl1;intrpos;while(lr){intmid(lr)/2;if(dist[mid]key){rmid;}else{lmid1;}}returnl;}intmain(){cinn;intpos0;for(inti1;in;i){cina[i];dist[pos]a[i];}sort(dist1,dist1n);//排序posunique(dist1,dist1n)-(dist1);//去重for(inti1;in;i){couta[i]离散化之后find(a[i],pos)endl;}return0;}离散化模版⼆ 排序使⽤哈希表去重并且记录离散化之后的值#includeiostream#includealgorithm#includeunordered_mapusingnamespacestd;constintN1e510;inta[N];intdist[N];intn;unordered_mapint,intid;// 原始的值, 离散之后的值intmain(){cinn;intpos0;for(inti1;in;i){cina[i];dist[pos]a[i];}sort(dist1,dist1n);//排序//离散化intcnt0;for(inti1;in;i){if(id.count(dist[i])){continue;}else{cnt;id[dist[i]]cnt;}}for(inti1;in;i){couta[i]离散化之后id[a[i]]endl;}return0;}2.1P1496 火烧赤壁解题思路题目给了n段着火的起始点和结束点我们根据这些数据算出总着火的路径这里可以用差分的思想利用给定的起始点和结束点就可以算出哪些路径起火但这里的数据范围过大创建不出那么大的数组我们要利用的是数据的对应下标所以利用离散化映射数据下标。代码#includeiostream#includealgorithm#includeunordered_mapusingnamespacestd;typedeflonglongLL;constintN2e410;LL a[N],b[N];LL dist[NN];LL f[NN];//差分intn;unordered_mapLL,intid;intmain(){cinn;intpos0;for(inti1;in;i){cina[i]b[i];dist[pos]a[i];dist[pos]b[i];}sort(dist1,dist1pos);posunique(dist1,dist1pos)-(dist1);for(inti1;ipos;i){id[dist[i]]i;}for(inti1;in;i){//用离散之后的数据差分f[id[a[i]]];f[id[b[i]]]--;}for(inti1;ipos;i){f[i]f[i]f[i-1];}intret0;for(inti1;ipos;i){intji;while(jposf[j]0){j;}//用原数据计算retdist[j]-dist[i];ij;}coutretendl;return0;}