[HDU517] 小奇的集合
2024-10-06 23:36:02
显然有贪心每次选择最大的两个数来做。
于是暴力地把最大的两个数调整到非负(暴力次数不超过1e5),接下来使用矩阵乘法即可。
\[\begin{pmatrix}
B'\\S'\\T'
\end{pmatrix}
=
\begin{pmatrix}
1&1&0\\
1&0&0\\
1&1&1
\end{pmatrix}
\begin{pmatrix}
B\\S\\T
\end{pmatrix}
\]
B'\\S'\\T'
\end{pmatrix}
=
\begin{pmatrix}
1&1&0\\
1&0&0\\
1&1&1
\end{pmatrix}
\begin{pmatrix}
B\\S\\T
\end{pmatrix}
\]
#include <bits/stdc++.h>
using namespace std;
const int mod=1e7+7;
struct Node {
int a[3][3];
int *operator[](const int&d) {return a[d];}
const int *operator[](const int&d) const{return a[d];}
Node operator*(const Node&b) const{
Node c;
memset(&c,0,sizeof c);
for(int i=0; i<3; ++i)
for(int k=0; k<3; ++k) if(a[i][k])
for(int j=0; j<3; ++j)
c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]%mod)%mod;
return c;
}
Node pow(int y) {
Node c,x=*this;
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j) c[i][j]=(i==j);
for(; y; y>>=1,x=x*x) if(y&1) c=c*x;
return c;
}
} G,M;
int n,k,sum,a[200010];
int main() {
scanf("%d%d",&n,&k);
for(int i=1; i<=n; ++i) {
scanf("%d",a+i);
sum=(sum+a[i]+mod)%mod;
}
sort(a+1,a+n+1);
while(a[n-1]<0&&k>0) {
a[n+1]=(a[n]+a[n-1]); n++; k--;
sum=(sum+a[n]+mod)%mod;
swap(a[n],a[n-1]);
}
if(k==0) {
printf("%d\n",sum);
return 0;
}
M[0][0]=a[n];
M[1][0]=a[n-1];
M[2][0]=sum;
G[0][0]=G[0][1]=1;
G[1][0]=1;
G[2][0]=G[2][1]=G[2][2]=1;
Node ans=G.pow(k)*M;
printf("%d\n",ans[2][0]);
return 0;
}
最新文章
- ThrottleAttribute
- [No000051]如何去掉word复制过来的文字背景色?
- js生成验证码并验证
- [Eclipse] Eclipse is running in a JRE, but a JDK is required
- 论--如何通过代码解析plist文件创建对应的控制器,以及控制器中的控件
- The CLR&#39;s Execution Model
- 二、搭建struts2的开发环境
- C#编程让Outlook乖乖交出帐户密码
- Alice&#39;s Chance
- Java语言程序设计(基础篇) 第八章 多维数组
- git(创建,提交,回退)
- Security+ 认证考过经验分享 802分飘过
- struts2简单入门-配置文件-struts.xml
- kettle连接mysql数据库并进行数据分析
- 使用selenium模拟登陆oschina
- go语言中常用的文件和文件夹操作函数
- 联通GWH-01路由猫超级用户登录方法
- 终于在nowcoder爆发了的懒惰
- python笔记之str常用方法
- 13 - stark总结、github代码
热门文章
- 使用root配置的hadoop启动时报错
- 【python / mxnet / gluoncv / jupyter notebook】基于mxnet和gluoncv的图像内容识别
- mysql之索引 应用于事物 内连接、左(外)连接、右(外)连接
- HAproxy负载均衡-ACL篇(转) blog.csdn.net/tantexian
- MyBatis Mapper Demo
- (转载)IDEA中对Git的常规操作(合并,提交,新建分支,更新)
- java源码-HashMap类设计
- SAP EXCEL OLE常用方法和属性
- python爬虫前提技术
- CentOS的SVN服务器搭建与自动部署全过程