Small cloth said: this time to share the algorithm some partial number theory, but you also do not be frightened by the number theory, in discrete mathematics, the content of elementary number theory is relatively simple content, ok, nonsense not to say more, the next step into the main topic

One, fast powers of integers

1. Introduction

The idea is to make it fasterIf the brute force algorithm is used, then the computer needs to calculateTime, ifIf it’s very large, then the time complexity is very large, but if you takeFast power algorithmThe time complexity is zeroGrade. How about that? Are you excited?

Principle 2.

The reason this algorithm is so fast is because it fits in with computer thinking, it takes advantage of binary.

For example, the decimal number 11 can be converted to a binary numberFrom left to right, the ones represent the decimal values.., so .

Ok, with the above example to help understand, let’s directly describe the principle of fast power algorithm:

  1. If you haveI multiply it by myself once, and then I getIf I multiply it by myself again, I get., autoTimes, we’re going to get.
  3. A decimal numberThere is a unique binary number that corresponds to it

The correctness of these three principles should not need to be proved!

3. Algorithm flow

For a power.

  1. willWrite it as a binary number
  2. Define a base , define a variable that stores the result .
  3. Traverse from right to leftIf the bit is, = , if the bit is, is itWhatever the bit is, is there always = .
  4. End of traversal, output

Let’s take a practical exampleFor example,

  1. =

  2. Define a base . .

  3. Traverse from right to left

    3.1 meet. = . = =

    3.2 meet.The same, = =

    3.3 meet. = = . = =

    3.4 meet. = * = , traversal completed

  4. The output

I’m sure you’ve got it by nowInteger fast powerThe beep

Two, matrix acceleration

1. Introduction

It’s an amazing algorithm, where you’re given a recursive relationship, and you’re asked to take the first order (It’s a big number, and if you were just recursing, it would be slow, but when you use matrix acceleration it gets really fast.

For example, for the Fibonacci sequence,, ask you for the firstThe value of the item

A lot of people have written blogs like this, sort of looking for patterns, and I don’t like doing that, so let me talk a little bit about what I do, how do I quickly find transition matrices

I’m going to do a simple mathematical derivation, which I believe you can all understand, and you can do the same thing when you run into something similar, and it’s very easy to find the transition matrix

The matrix is really hard to hit (whisper BB

So here we have it, and the rest of the matrix quick powers just a little bit of a jumble, so let’s talk about the matrix quick powers

Three, quick powers of matrices

1. Introduction

I do not know if you have learned linear algebra, matrix is a very important knowledge of line generation, if some children have not learned or too long forgotten, I can help you review the relevant important knowledge points

I really don’t want to type matrix, here is not important to use words to describe it

1. Addition

Requirements: homotype matrix, that is, two matrices of the same size, are.

Operation: add the numbers at the corresponding positions of the two matrices

2. Subtraction operation

It’s the inverse of addition. I won’t go over it

3. Multiplication operation

Requirement: a number multiplied by a matrix

Action: Multiply the elements in each position of the matrix by this number

4. Highlight, key points, matrix multiplication

Matrix times A matrix requires: matrix A times matrix B, you have to know that the size of matrix A is zero, then the scale of B isThat is, the number of columns of A is equal to the number of rows of B

Action: as shown below (play matrix too tired

Matrix multiplication is associative

So with that in mind, you’ll see that we’re back to our original fast powers problem, except now instead of multiplying two integers, we’re multiplying two matrices, so we just have to reloadOperator, the other is not much different from integer fast powers, right

1. Data structure

struct Mat { ll m[MAXN][MAXN]; // Initializes all elements of the matrix to 0Mat() { memset(m, 0, sizeof(m)); } // Call this function to initialize the identity matrix voidbuild () {
        for(int i = 1; i <= n; i++) { m[i][i] = 1; }}};Copy the code

The identity matrix is a matrix where the diagonal from the top left to the bottom right is 1 and everything else is 0

Overloaded operator

Mat operator* (const Mat& a, const Mat& b) {
    Mat c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++) { c.m[i][j] = c.m[i][j] + a.m[i][k] * b.m[k][j]; }}}return c;
}
Copy the code

Fast power body

while (k > 0) {
    if (k & 1) {
        ans = ans * mat;
    }
    mat = mat * mat;
    k >>= 1;
}
Copy the code

Note that the *= operator cannot be used here because there is no overload

And then we’re done

Code word is not easy, if this article can help you, please click a like and then go, a like from you will be a great encouragement to me, ^_^!