红鲤鱼与绿鲤鱼与驴

今天学习 二分法 and 快速幂

二分查找函数：
在一个升序数组的 begin 和 end 前闭后开区间内进行二分查找
lower_bound (begin,end,val) 返回大于或等于val的第一个元素位置
upper_bound (begin,end,val) 返回大于val的第一个元素位置
如果所有元素都小于 val 则返回 end 的位置
补充：头文件：algorithm

如果要二分的是个小数 需要规定精度

double left,right,mid;
while(right - left > eps ){
    mid = (right + left) / 2;
    if( judge(mid) ) 
        left = mid;
    else 
        right = mid;
}
return mid;

二分答案
二分枚举答案，由于进行二分，所以复杂度 log(n)，比直接 for 的时间更短。
1、适用情况：求最值，可能答案区间有限且单调且大于零，检验答案合理性复杂度低
2、题目标志：最小值最大、最大值最小
3、模板代码：

while (l <= r){
    int mid = (l + r) >> 1;//右移 效果相当于除以二
    if (judge(mid)){
        ans = mid;
        l = mid + 1;
    }else
        r=mid - 1;
}
return ans ;

4、例题1 SP297 AGGRCOW - Aggressive cows：
https://www.luogu.com.cn/problem/SP297

题意：有n个牛栏，分别位于X1,X2...Xn 选m个放进牛 使得相邻牛之间的最小距离值最大

思路：先对隔间编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x，如果判断出最小差值为x时可以放下m头牛，说明当前的x有点小，就先让x变大再判断；如果放不下，说明当前的x太大了，就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。

#include<iostream>
#include<algorithm>
using namespace std;
int n,c;
int a[100005];
int judge(int m){
    int num=1,cnt=1;
    for(int i=2;i<=n;i++){
        if(a[i]-a[num]>=m){
            cnt++;
            num=i;
            if(cnt==c)
                return 1;
        }
    }
    return 0;
}
int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n>>c;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        int l=1,r=a[n];
        while(l<r){
            int m=(l+r+1)/2;
            if(judge(m))
                l=m;
            else
                r=m-1;
        }
        cout<<l<<endl;
    }
    return 0;
}

5、例题2 CF39H Multiplication Table：
https://www.luogu.com.cn/problem/CF448D

题意：有 n * m 乘法表，将 n * m 个数从小到大依次排列，第K个数是多少?

思路：由于数据既大且多，暴力构造乘法表然后排序的做法不可取。正确做法是使用二分查找。由于乘法表有个特殊的公式，即对于一个数X，X除以行数i 设得到的结果（整数表示）为Q，如果Q大于列数M,那么这个数就大于第i行所有的数，如果等于列数，说明这个数是第i行第Q大的数。如果小于列数，说明这个数比第i行前Q个数大。利用这一点查找mid在乘法表中所处的位置，然后判断mid与k的大小关系进而确定左右边界继续二分，直到找到该位置（左等于右）。 

#include<iostream>
using namespace std;
int main()
{
    long long n,m,k;
      cin>>n>>m>>k;
     long long l=1,r=n*m;
     while(l<r){
        long long mid=(l+r)/2,num=0;
         for(long long i=1;i<=n;i++){
              long long q=mid/i;
              if(q>m)
                  num+=m;
              else 
                  num+=q;
        }   
        if(num>=k)
            r=mid;
        else 
            l=mid+1;
     }
    cout<<l<<endl;
    return 0;
}

———————————————————— 分 界 线 ————————————————————

快速幂： ( a ^ b ) mod p 

int power(int a,int b,int p){
    int ans = 1 % p;
    for(;b;b>>=1){
        if( b & 1 )
            ans=(long long)ans * a % p;
        a=(long long)a * a % p;
    }
    return ans;
}

矩阵快速幂：将快速幂中的底数变为矩阵 线性递推式
模板题：https://www.luogu.com.cn/problem/P3390

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int MAXN = 105;
struct Mat {
    ll m[MAXN][MAXN];
}ans;
Mat Mul(Mat a, Mat b, ll n) {//计算矩阵a乘矩阵b，n为矩阵的大小
    Mat c;
    memset(c.m, 0, sizeof(c.m));
    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]) % mod) % mod;
    return c;
}
Mat Mul_power(Mat a, ll b, ll n) {//计算a^b，n为矩阵的大小
    for (int i = 1; i <= n; i++)//构造单位矩阵
        ans.m[i][i] = 1;
    while (b) {
        if (b & 1)
            ans = Mul(ans, a, n);
        a = Mul(a, a, n);
        b >>= 1;
    }
    return ans;
}
int main() {
    ll n;
    ll k;
    cin>>n>>k;
    Mat zls;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>zls.m[i][j];
    Mat zlss=Mul_power(zls,k,n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cout<<zlss.m[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

自言自语Part：
晚上有时间的话就把习题做了在发一篇 Day 1.5
Good Luck! 今天还算顺利