bzoj 3231 [Sdoi2008]递归数列——矩阵乘法
2024-09-04 05:14:41
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3231
矩阵乘法裸题。
1018是10^18。别忘了开long long。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=;
int n;
ll L,R,b[N],c[N],mod,s[N],prn;
struct Matrix{
ll a[N][N];
Matrix(){memset(a,,sizeof a);}
void init()
{
for(int i=;i<n;i++)a[i][]=c[i];
for(int i=;i<n;i++)a[i-][i]=;
a[][n]=a[n][n]=;
}
Matrix operator* (const Matrix &b)const
{
Matrix c;
for(int i=;i<=n;i++)
for(int k=;k<=n;k++)
for(int j=;j<=n;j++)
(c.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
return c;
}
}ans,r,yans,yr;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&b[i]);
s[i]=s[i-]+b[i];
ans.a[][n-i+]=b[i];
}
ans.a[][n+]=s[n-];
yans=ans;
for(int i=;i<=n;i++)scanf("%lld",&c[i]);
scanf("%lld%lld%lld",&L,&R,&mod);
n++;r.init();yr=r;
if(R<n)prn=s[R];
else
{
ll k=R-n+;
while(k)
{
if(k&)ans=ans*r;
r=r*r;k>>=1ll;
}
prn=(ans.a[][n]+ans.a[][])%mod;
}
if(L-<n)prn=((prn-s[L-])%mod+mod)%mod;
else
{
ll k=L--n+;
while(k)
{
if(k&)yans=yans*yr;
yr=yr*yr;k>>=1ll;
}
prn=((prn-yans.a[][n]-yans.a[][])%mod+mod)%mod;
}
printf("%lld\n",prn);
return ;
}
最新文章
- mysql基准测试
- 软件工程--界面UI 的原型设计
- sp_configure错误:不支持对系统目录进行即席更新。
- 转一篇介绍Web session概念的文章
- ServiceStack.Text反序列化lowercase_underscore_names格式的JSON
- java数组初始化
- php大力力 [035节] 先记录一些链接
- DeepLearning常用库简要介绍与对比
- java:抽象类和抽象函数
- Quartz定时任务学习(二)web应用
- python字典构造函数dict(mapping)解析
- python pyinstaller打包exe暗坑1
- 使用Mongodb+Shiro+SpringMVC实现动态权限分配
- PHP连接MySQL查询中文时显示Notice: Trying to get property of non-object
- Js将数字转化为中文大写
- 向量体系结构(2)----SIMD指令集扩展和GPU
- wamp添加本地虚拟域名
- PHI 数据库简介
- openjdk源码阅读导航
- Linux中Readlink命令
热门文章
- linux nload命令简介及安装方法
- 关于将ECharts引入到项目中的几种方式
- 莫烦pytorch学习笔记(八)——卷积神经网络(手写数字识别实现)
- com.rabbitmq.client.ShutdownSignalException: channel error; protocol method: #method<;channel.close>;(reply-code=404, reply-text=NOT_FOUND - no queue &#39;springCloudBus.anonymous.6Xa99MDZTJyHKdPqMyoVEA&#39; in
- CSS动画之transition属性
- PAT甲级——A1008 Elevator
- 一次读懂mybatis中的缓存机制
- <;每日一题>;题目22:简单的python练习题(31-40)
- css3之文本text-overflow 与 word-wrap, word-break
- linux删除登录日志及历史命令