当前位置:网站首页>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;
}
边栏推荐
- Oracle ORA error message
- mysql关于自增长增长问题
- Conditionally [jsonignore]
- Stc8h development (XII): I2C drive AT24C08, at24c32 series EEPROM storage
- 阿里测试师用UI自动化测试实现元素定位
- What is the difference between gateway address and IP address in tcp/ip protocol?
- How to standardize the deployment of automated testing?
- MySQL master-slave replication
- Class A, B, C networks and subnet masks in IPv4
- ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
猜你喜欢
Blue Bridge Cup - Castle formula
An article will give you a comprehensive understanding of the internal and external components of "computer"
Simple blog system
Web components series (VII) -- life cycle of custom components
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
简易博客系统
Detailed explanation of serialization and deserialization
C language -- structs, unions, enumerations, and custom types
随机推荐
Stc8h development (XII): I2C drive AT24C08, at24c32 series EEPROM storage
Tips for using dm8huge table
Plus d'un milliard d'utilisateurs de grandes entreprises comme Facebook ont été compromis, il est temps de se concentrer sur le did
20、 EEPROM memory (AT24C02) (similar to AD)
ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
TCP/IP协议里面的网关地址和ip地址有什么区别?
[disassembly] a visual air fryer. By the way, analyze the internal circuit
【leetcode】22. bracket-generating
User experience index system
Cf464e the classic problem [shortest path, chairman tree]
如何修改表中的字段约束条件(类型,default, null等)
Flask learning and project practice 8: introduction and use of cookies and sessions
Factors affecting user perception
自动化测试怎么规范部署?
Global and Chinese market of plasma separator 2022-2028: Research Report on technology, participants, trends, market size and share
Differential GPS RTK thousand search
Custom event of C (31)
Error 1045 (28000): access denied for user 'root' @ 'localhost' (using password: no/yes
Record an excel xxE vulnerability