2/11 matrix fast power +dp+ bisection

Matrix fast power template problem ：
It can solve the problem of large data scale , But there are recursion formulas

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,k;
struct Matrix
{
    
	static const int N=102;  // Open matrix 
	ll a[N][N];
	Matrix(ll e=0)          // Matrix Qing 0
	{
    
		for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            a[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B)   // Multiplication of matrices  A*B
	{
    
		Matrix ans(0);    // Initialize all to 0 Matrix 
		for (int i=1;i<=n;i++)
        {
    
			for (int j=1;j<=n;j++)
			{
    
				for (int k=1;k<=n;k++)  
				{
    			// Analog multiplication 
					ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
				}
			}
		}
		return ans;  // return 
	}
	Matrix ksm(Matrix A,ll b){
    
		Matrix ans(1);   // Initialize all to 1 Matrix 
		while (b)
        {
    
			if (b&1)ans=mul(ans,A);   // Fast power 
			A=mul(A,A);
			b>>=1;
		}
		return ans;
	}
};
int main()
{
    
    scanf("%lld%lld",&n,&k);
	Matrix tmp;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=n;j++)
            cin>>tmp.a[i][j];
    }
    tmp=tmp.ksm(tmp,k);
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=n;j++)
            cout<<tmp.a[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

https://www.luogu.com.cn/problem/P1103
The difficulty is
Determine the meaning of the array
and
Design state transition equation

#include <bits/stdc++.h>

using namespace std;
const int mod=1e6+7;
const int inf=0x3f3f3f3f;
int f[105][105],n,k,m,a[105],minn=inf;
struct book
{
    
    int h,w;
}e[105];
bool cmp(book e1,book e2)
{
    
    return e1.h<e2.h;
}
int main()
{
    
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&e[i].h,&e[i].w);
    sort(e+1,e+n+1,cmp);
    memset(f,inf,sizeof(f));
    for(int i=1;i<=n;i++)
    {
    
        f[i][1]=0;
    }
    for(int i=2;i<=n;i++)    // Indicates which book to add 
    {
    
        for(int j=1;j<i;j++)  // And j This book is adjacent 
        {
    
            for(int len=2;len<=min(i,n-k);len++)  // The number of books currently selected 
                f[i][len]=min(f[i][len],f[j][len-1]+abs(e[i].w-e[j].w));
        }
    }
    for(int i=n-k;i<=n;i++)
        minn=min(minn,f[i][n-k]);
    cout<<minn<<endl;
    return 0;
}

https://www.luogu.com.cn/problem/P1182
The maximum is the smallest

while(l<r)
{
    
    int mid=(l+r)>>1;
    if(check(mid))     // The quantity distributed exceeds the demand , return 1
         l=mid+1;
    else
         r=mid;
}

The minimum is the maximum ：

while(l<r)
{
    
    int mid=(l+r+1)>>1;
    if(check(mid))     // The quantity divided is less than the demand , return 1
        r=mid-1;
    else
        l=mid;
}

#include <bits/stdc++.h>

using namespace std;
const int mod=1e6+7;
const int inf=0x3f3f3f3f;
int n,m,a[100005],l,r;
int check(int x)
{
    
    int sum=0,num=0;
    for(int i=1;i<=n;i++)
    {
    
        if(sum+a[i]<=x)
            sum+=a[i];
        else
            sum=a[i],num++;
    }
    return num>=m;   // The number of points is greater than the required number of questions , explain x It's worth less 
}
int main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    
        scanf("%d",&a[i]);
        l=max(l,a[i]);
        r+=a[i];
    }
    while(l<r)            // The template with the minimum maximum 
    {
    
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    cout<<l<<endl;
    return 0;
}