算法笔记 前缀和 差分 快速幂(C/C++)

    早上起来，室友还在睡，没法尽情敲代码，所以闲得无聊去逛了下某介于AC间的小破站，复习了一下一些基础算法。也就是tags和标题中也有写到的前缀和、差分和快速幂。首先呢，还是必须得感谢下阿婆主的视频讲解的，确实比直接看代码什么的来得形象很多。在此记录一下，也是我对学习的理解和笔记吧。

贴出老哥的视频，文章大部分内容也是来源于老哥的视频  【AgOHの算法胡扯】   的【AgOHの算法胡扯】前缀和 差分 快速幂

---

前言

    可能小伙伴们会说，现在都有视频学习了，干嘛还去逛文章看啊，生涩难懂不如视频来得简单粗暴。这里分享一下我从很多的阿婆主以及博客主那儿得来的，也算是我自己的一个偏见吧：

    视频学习虽然大部分来得生动形象，但是讲真的，很佷很费时间！！！现在的视频，除非是一些大学的公开课那种，又或者是良心阿婆主，否则大多数（起码我的感觉，或者偏见是这样）都是长于20分钟的，哪怕你是3倍速看视频，忽略大脑是否能反应得过来，也忽略你对知识的遗忘速度，但是你还是得跟着视频走一遍。否则很多时候你如果跳着看视频的话，是容易看不懂他说的啥的，因为大多数视频是没有给你标时间点的，你不会知道他哪个点在说哪个知识点。

    然后再说文章和博客，虽然可能取决于博主和作者的思维和写作水平，但是文章一类的才是真真的简单粗暴！你可以自由地己获取你想要的部分。一般的文章都是会有自己的目录的，根据你想要的获取的具体知识点，重点跳到你想要看的地方，反复阅读。而且一般情况下（能学懂的前提），是比视频学习的效率高出很多的，同样地20分钟，看一些学习视频你最多看1遍，但是同内容而言文章够你看好几遍的了。

    当然也不是说视频不好，感觉可能视频是适合初学入门吧，生动形象，能及时跟着视频主的思路走。

前缀和

问题描述

    现有一段数组，求出[l,r]内的所有数的和。

分析

可以用暴力，线段树，以及将介绍的前缀和

预处理

    在读入数组a的时候（也就是cin或者scanf的时候），构建一个数组d，d[i]=d[i-1]+a[i];

    也就是说d[i]实际上为a的前i项和

见表：

name/index	0	1	2	3	4	5
a	\	2	6	8	4	3
d	0	2	8	16	20	23

输出

    输出即为d[r]-d[l-1]

差分

问题描述

    
现有长度为n的数字序列，对其进行m次的区间修改（把某区间内的所有数加减一个值），输出改后的序列。

分析

可以用暴力，线段树，以及将介绍的差分

预处理

（同上）

    在读入数组a的时候（也就是cin或者scanf的时候），构建一个数组d，d[i]=a[i]-a[i-1];

    也就是说d[i]实际上为a的相邻两项的差值

见表：

name/index	0	1	2	3	4	5
a	\	2	6	8	4	3
d	\	2	4	2	-4	-1

    且a[i]=d[1]+……+d[i]

修改

    
举个栗子来说吧，如对于上述表，对[2,4]都+5处理，那么

见表：

name/index	0	1	2	3	4	5
a	\	2	11	13	9	3
d	\	2	9	2	-4	-6

    你会发现，其实就是序号2和5的位置处d值改变了下

那么推广：

    对于[l,r]的区间进行了+k（k可以取负）操作，那么只需要把d[l]+=k;而把d[r+1]-=k处理就行了

输出

    按照前面提到的，利用a[i]=d[1]+……+d[i]的原理，输出a中所有的值即可

快速幂

问题描述

    这个应该很简单了，求 a^b % p。

分析

直接算的话，可以很清楚地料想到，会有对应的b次乘积操作。但是运用快速幂的方法，会减少很多次乘积操作

举栗子

    假如求a⁸ (默认mod 1吧)

a * a = a²

a² * a² = a⁴

a⁴ * a⁴ = a⁸



    done!

    所以，对于本该8次的乘积操作，先只需要3次！

    那么这是b为2的整数次方，其他情况呢

    例如a¹³ (默认 %1)呢，

    可以利用a^{m * n}=a^m * aⁿ 的原理

    a¹³ = a⁸ * a⁴ * a;

    乘积操作次数=3+2+1=6次，而非原来的13次

p.s..可以在算a⁸的过程中，把过程中a⁴、a²的值用一个数组存起来（记忆化），那么实际上的次数就变成了max(3,2,1)+1+1=5次了

！！！注意每次操作别忘了%p！！！

输出

    return最后的结果就可以了

快速幂的模板

#include<iostream>

using namespace std;

int power(int a, int b, int m) {
    int ans = 1;  a %= m;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

int main()
{
    int a, b, p;
    while (cin >> a >> b >> p) {
        if (p == -1 && a == -1 && b == -1) break;
        cout << power(a, b, p) << endl;
    }

    return 0;
}

HDOJ 1061

Rightmost Digit Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)

Problem Description
    Given a positive integer N, you should output the most right digit of N^N.

Input
    The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output
    For each test case, you should output the rightmost digit of N^N.

Sample Input
2
3
4

Sample Output
7
6

Hint

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

AC代码：

#include<iostream>

using namespace std;
int power(int a, int b, int m){
    int ans = 1;  a %= m;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

int main(){
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        cout<<power(m,m,10)<<endl;
    }
    return 0;
}

Author
    Ignatius.L

参考

感谢 【AgOHの算法胡扯】   的 【AgOHの算法胡扯】前缀和 差分 快速幂