lint0949. lint0140.

949. Fibonacci II

keyword:快速幂,二进制, 记忆化

计算Fibonacci数列第n项的最后四个数字，也就是 %1000的值
In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:0,1,1,2,3,5,8,13,21,34,…
An alternative formula for the Fibonacci sequence is:

lint0949-1.png

Given an integer n, your goal is to compute the last 4 digits of Fn

Example

Given: n = 9
Return: 34

Notice

1.0 ≤ n ≤ 1,000,000,000
2.If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros(print Fn mod 10000)

• 本题出自「POJ3070」Fibonacci
• 这道题用到了矩阵快速幂，第一个问题什么是快速幂，快速幂是指利用矩阵的乘法结合律来实现快速计算矩阵幂的过程。
  矩阵快速幂和整数快速幂是一样的原理，a⁸ 如果一个一个乘，那么要计算7次。但是如果按((a²)²)²,则只计算4次，也就是一个是O(n)的时间复杂度，一个是O(log_n), 而程序的实现怎么做呢？快速幂好理解，但是实现起来不好办。

要计算a^b, 最快的方式就是尽可能少用a*a，仅仅a²用a*a, 其他的幂，仅仅利用a*a的结果(记忆化，并且记忆化贯穿始终)，但是不用a*a的过程，也就是完全用a的2的乘方次幂相乘
a² = a¹*a¹, 权值*权值
a³ = a¹*a², 已有结果*权值
a⁴ = a²*a², 权值*权值
a⁵ = a¹*a⁴, 已有结果*权值
a⁶ = a²*a⁴, 已有结果*权值
a⁷ = a¹*a²*a⁴, 已有结果*权值,
a⁸ = a⁴*a⁴, 权值*权值
a¹⁹=a^(24+21+20), 19的二进制10011，19 = 2⁴ + 2¹ + 2⁰，因此我们将a¹⁹ 转换为算 a¹⁶ * a² * a¹, 当然这里面用到了x^m*xⁿ = x^m+n

int quick_pow(int a,int b)
{
    int weight= a;//初始化权值
    int ret = 1;//初始化结果
    while(b){
        if(b&1){//判断b的最后一位是否为1
            ret *= weight;
        }
        weight *= weight;//更新权值
        b >>= 1;
    }
    return ret;
}

• 对于矩阵的幂，原理是一样的，只是两个矩阵相乘又比较复杂，需要单独的函数来完成，比如下面的函数

 c = a*b
a[0][0] a[0][1] b[0][0] b[0][1] c[0][0] c[0][1]
a[1][0] a[1][1] b[1][0] b[1][1] c[1][0] c[1][1]

i=0 j=0:   i  k    k  j
c[0][0]+=a[0][0]*b[0][0] k=0
c[0][0]+=a[0][1]*b[1][0] k=1
i=0 j=1:   i  k    k  j
c[0][1]+=a[0][0]*b[0][1] k=0
c[0][1]+=a[0][1]*b[1][1] k=1
i=1 j=0:   i  k    k  j
c[1][0]+=a[1][0]*b[0][0] k=0
c[1][0]+=a[1][1]*b[1][0] k=1
i=1 j=1:   i  k    k  j
c[1][1]+=a[1][0]*b[0][1] k=0
c[1][1]+=a[1][1]*b[1][1] k=1

void multi_mtrx1(int a[2][2],int b[2][2])
{
   int i,j,k;
   int c[2][2];
   memset(c,0,sizeof(c));
   for(i=0;i<2;i++){
      for(j=0;j<2;j++){
         for(k=0;k<2;k++){
            c[i][j]+=a[i][k]*b[k][j];
            c[i][j]%=10000;/*加上这一句*/
         }
      }
   }
   for(i=0;i<2;i++)
      for(j=0;j<2;j++)
         a[i][j]=c[i][j];
}

• 另外一个矩阵乘法函数 以及快速幂的函数

 /* 这种方法比较难于理解,好处是如果n比较大,且矩阵比较稀疏的时候可以剪枝
i=0 k=0: i k k j
c[0][0]+=a[0][0]*b[0][0] j=0
c[0][1]+=a[0][0]*b[0][1] j=1
i=0 k=1: i k k j
c[0][0]+=a[0][1]*b[1][0] j=0
c[0][1]+=a[0][1]*b[1][1] j=1
i=1 k=0: i k k j
c[1][0]+=a[1][0]*b[0][0] j=0
c[1][1]+=a[1][0]*b[0][1] j=1
i=1 k=1: i k k j
c[1][0]+=a[1][1]*b[1][0] j=0
c[1][1]+=a[1][1]*b[1][1] j=1
*/
void multi_mtrx2(int a[2][2],int b[2][2])
{
   int i,j,k;
   int c[2][2];
   memset(c,0,sizeof(c));
   for(i=0;i<2;i++){
      for(k=0;k<2;k++)
      {
         if(0==a[i][k])/*剪枝,但其实对于2x2的矩阵意义不大*/
            continue;

         for(j=0;j<2;j++){
            c[i][j]+=a[i][k]*b[k][j];
            c[i][j]%=10000;/*加上这一句*/
         }
      }
   }
   for(i=0;i<2;i++)
      for(j=0;j<2;j++)
         a[i][j]=c[i][j];
}

void quick_pow(int ret[2][2],int power)
{
   int fi[2][2];
   ret[0][0]=ret[1][1]=1;
   ret[0][1]=ret[1][0]=0;
   fi[1][1]=0;
   fi[0][0]=fi[0][1]=fi[1][0]=1;
   while(power){
      if(power&1)
         multi_mtrx2(ret,fi);
      multi_mtrx2(fi,fi);
      power>>=1;
   }
}

• Java版

public class Solution {
    public String lastFourDigitsOfFn(int n) {
        if (n == 0) return "0";
        if (n == 1) return "0001";
        int[][] f = {{1, 1}, {1, 0}};
        int[][] res = powHelper(f, n-1);
        String s = "" + res[0][0];
        if (s.length() == 1) return "000" + s;
        if (s.length() == 2) return "00" + s;
        if (s.length() == 3) return "0" + s;
        return s;
    }
    private int[][] powHelper(int[][] f, int n) {
        if (n == 1) return f;
        if (n == 2) return multipyHelper(f, f);
        int[][] ans =  powHelper(powHelper(f, n/2), 2);
        if (n % 2 == 0) return ans;
        return multipyHelper(f, ans);
    }
    private int[][] multipyHelper(int[][] f1, int[][] f2) {
        // f[0][0] f[0][1]
        // f[1][0] f[1][1]
        int n = 10000;
        int x = (f1[0][0]*f2[0][0]%n + f1[0][1]*f2[1][0]%n)%n;
        int y = (f1[0][0]*f2[0][1]%n + f1[0][1]*f2[1][1]%n)%n;
        int p = (f1[1][0]*f2[0][0]%n + f1[1][1]*f2[1][0]%n)%n;
        int q = (f1[1][0]*f2[0][1]%n + f1[1][1]*f2[1][1]%n)%n;
        return new int[][]{{x, y},{p, q}};
    }
}

lint0140. Fast Power

Calculate the aⁿ % b where a, b and n are all 32bit positive integers.
特别注意的是一个表达式必须完全计算完才能mod b,不可用中间结果mod操作

快速幂版

public class Solution {
    /**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        long weight = a;
        long ret = 1;
        while(n!=0){
            if((n&0x1)==1){
                ret = (ret*weight) % b;//不可用 ret*=(weight%b)
            }
            weight = (weight*weight) % b;//不可用 weight *= (weight%b)
            n >>= 1;
        }
        return (int)ret%b;
    }
}

递归版

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        }
        if (n == 0) {
            return 1 % b;
        }
        
        long product = fastPower(a, b, n / 2);
        product = (product * product) % b;
        if (n % 2 == 1) {
            product = (product * a) % b;
        }
        return (int) product;
    }
};