当前位置:网站首页>2/11 matrix fast power +dp+ bisection
2/11 matrix fast power +dp+ bisection
2022-07-06 04:03:00 【Zhong Zhongzhong】
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;
}
边栏推荐
- User datagram protocol UDP
- Ybtoj coloring plan [tree chain dissection, segment tree, tarjan]
- Basic knowledge of binary tree, BFC, DFS
- MySql数据库root账户无法远程登陆解决办法
- [adjustable delay network] development of FPGA based adjustable delay network system Verilog
- Global and Chinese market of rubber wheel wedges 2022-2028: Research Report on technology, participants, trends, market size and share
- Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
- Leetcode32 longest valid bracket (dynamic programming difficult problem)
- Stack and queue
- How to modify field constraints (type, default, null, etc.) in a table
猜你喜欢
Ks008 SSM based press release system
MySql數據庫root賬戶無法遠程登陸解决辦法
Serial port-rs232-rs485-ttl
How to standardize the deployment of automated testing?
Thread sleep, thread sleep application scenarios
How to modify field constraints (type, default, null, etc.) in a table
Flask learning and project practice 8: introduction and use of cookies and sessions
Cf464e the classic problem [shortest path, chairman tree]
[Massey] Massey font format and typesetting requirements
JVM的手术刀式剖析——一文带你窥探JVM的秘密
随机推荐
Microkernel structure understanding
MySql数据库root账户无法远程登陆解决办法
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
What is the difference between gateway address and IP address in tcp/ip protocol?
KS003基于JSP和Servlet实现的商城系统
C language -- structs, unions, enumerations, and custom types
User datagram protocol UDP
How to standardize the deployment of automated testing?
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Viewing and verifying backup sets using dmrman
mysql关于自增长增长问题
【按键消抖】基于FPGA的按键消抖模块开发
自动化测试的好处
有条件地 [JsonIgnore]
综合能力测评系统
如何修改表中的字段约束条件(类型,default, null等)
3分钟带你了解微信小程序开发
C form application of C (27)
C (thirty) C combobox listview TreeView
MySQL transaction isolation level