快速幂，错位排序笔记
记一下刚学明白的快速幂和错位排序的原理和代码
快速幂
原理：
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=0
if(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）
- 假设第k个物品不放到第n个位置上：
先对前n-1个物品进行错位排列（Dn-1），
再把第n个物品放到前n-1任意一个位置上（n-1）
Dn-1*（n-1） - 假设第k个物品放到第n个位置上：
其他n-2个物品进行错位排序（Dn-2）
k可以是1~n-1中任意一个数（n-1）
Dn-2*（n-1）