快速幂，错位排序笔记

​
记一下刚学明白的快速幂和错位排序的原理和代码

快速幂

原理：
a^b= (a^（b/2）) ^ 2（b为偶数）
a^b = a*（a^（ (b-1)/2））^2（b为奇数）

指数为偶数时，底数a直接平方

质数为奇数时，结果*当前底数a，a再平方

然后指数除以2

赞美deepseek，公式画的好清楚。

把O(n)时间复杂度的幂乘优化成log(n)的算法。

int fastPow(int a, int b){int res = 1;while(b){//b不为0时，拆分指数b，直到b=0if(b&1) res = res*a;//如果b是奇数，那么b的二进制形式最后一位是1，b&1=1//如果b是偶数，b的二进制形式最后一位是0，b&1=0       a = a*a;b >> 1;//b二进制形势下右移一位，相当于b=b/2}
}

错位排序

递推公式
设有从1到n共n个需要错位排序的东西
Dn为n个东西可以错位排序的总数
Dn=(n-1)(Dn-1+Dn-2)
代码片：

D[1]=0,D[2]=1;
for(int i = 3; i <= n; i++){D[i]=(i-1)*(D[i-1]+D[i-2]);
}

其中D1=0，D2=1
推导：
设第n个物品在第n个位置上，考虑有第k个物品。（1 <= k <= n-1）

1. 假设第k个物品不放到第n个位置上：
   先对前n-1个物品进行错位排列（Dn-1），
   再把第n个物品放到前n-1任意一个位置上（n-1）
   Dn-1*（n-1）
2. 假设第k个物品放到第n个位置上：
   其他n-2个物品进行错位排序（Dn-2）
   k可以是1~n-1中任意一个数（n-1）
   Dn-2*（n-1）

​