数学其它

---

快速幂

以下是快速幂的模板

int fastPow(int a,int n){//计算aⁿ
   int ans=1; //用ans返回结果
   while(n){  //把n看成二进制数，逐个处理它最后一位
       if(n&1) ans*=a;  //&按位与操作，如果n的最后一位是1，表示这个地方需要参与计算
       a*=a; //递推：2次方--4次方--八次方···
       n>>=1; //n右移一位，把刚处理过的n的最后一位去掉
   }
    return ans;
}

通常题目都会要求模p，根据模的性质：

$$(a+b)\ \% \ p = (a \% p \ + \ b \% p)\ \% p$$

$$(a \times b)\ \% \ p = (a \% p \ \times b \% p) \ \% p$$

得到取模的快速幂模板为

using ull = unsigned long long;
ull fp(ull a,ull n){
    ull ans = 1;
    while(n){
        if(n & 1) ans = (ans%p * a%p) %p;
        a = (a%p * a%p) %p;
        n >>= 1;
    }
    return ans;
}

---

各种定理

中位数定理：

要将一个有序数组通过+1或-1的n次操作变换为全部相等数所需的操作次数，就是每个数变换为中位数的操作次数之和

带权中位数：

和中位数定理差不多，都是找中位数，此类问题最优解就在“刚刚过半”这里

---