当前位置:网站首页>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;
}
边栏推荐
- Ybtoj coloring plan [tree chain dissection, segment tree, tarjan]
- How do we make money in agriculture, rural areas and farmers? 100% for reference
- Leetcode32 longest valid bracket (dynamic programming difficult problem)
- [FPGA tutorial case 11] design and implementation of divider based on vivado core
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
- Global and Chinese markets for medical gas manifolds 2022-2028: Research Report on technology, participants, trends, market size and share
- Facebook and other large companies have leaked more than one billion user data, and it is time to pay attention to did
- 【leetcode】1189. Maximum number of "balloons"
- mysql关于自增长增长问题
- Yyds dry goods inventory web components series (VII) -- life cycle of custom components
猜你喜欢
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Microkernel structure understanding
How do we make money in agriculture, rural areas and farmers? 100% for reference
Blue Bridge Cup - day of week
Database, relational database and NoSQL non relational database
MySql數據庫root賬戶無法遠程登陸解决辦法
User experience index system
Maxay paper latex template description
JVM的手术刀式剖析——一文带你窥探JVM的秘密
Serial port-rs232-rs485-ttl
随机推荐
Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
Do you know cookies, sessions, tokens?
math_极限&微分&导数&微商/对数函数的导函数推导(导数定义极限法)/指数函数求导公式推导(反函数求导法则/对数求导法)
Prime Protocol宣布在Moonbeam上的跨链互连应用程序
[matlab] - draw a five-star red flag
Benefits of automated testing
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
Tips for using dm8huge table
WPF effect Article 191 box selection listbox
自动化测试怎么规范部署?
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
C mouse event and keyboard event of C (XXVIII)
Blue Bridge Cup - Castle formula
Oracle ORA error message
User datagram protocol UDP
3分钟带你了解微信小程序开发
Redis (replicate dictionary server) cache
[adjustable delay network] development of FPGA based adjustable delay network system Verilog