题目: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 ;
}

最新文章

  1. mysql基准测试
  2. 软件工程--界面UI 的原型设计
  3. sp_configure错误:不支持对系统目录进行即席更新。
  4. 转一篇介绍Web session概念的文章
  5. ServiceStack.Text反序列化lowercase_underscore_names格式的JSON
  6. java数组初始化
  7. php大力力 [035节] 先记录一些链接
  8. DeepLearning常用库简要介绍与对比
  9. java:抽象类和抽象函数
  10. Quartz定时任务学习(二)web应用
  11. python字典构造函数dict(mapping)解析
  12. python pyinstaller打包exe暗坑1
  13. 使用Mongodb+Shiro+SpringMVC实现动态权限分配
  14. PHP连接MySQL查询中文时显示Notice: Trying to get property of non-object
  15. Js将数字转化为中文大写
  16. 向量体系结构(2)----SIMD指令集扩展和GPU
  17. wamp添加本地虚拟域名
  18. PHI 数据库简介
  19. openjdk源码阅读导航
  20. Linux中Readlink命令

热门文章

  1. linux nload命令简介及安装方法
  2. 关于将ECharts引入到项目中的几种方式
  3. 莫烦pytorch学习笔记(八)——卷积神经网络(手写数字识别实现)
  4. com.rabbitmq.client.ShutdownSignalException: channel error; protocol method: #method&lt;channel.close&gt;(reply-code=404, reply-text=NOT_FOUND - no queue &#39;springCloudBus.anonymous.6Xa99MDZTJyHKdPqMyoVEA&#39; in
  5. CSS动画之transition属性
  6. PAT甲级——A1008 Elevator
  7. 一次读懂mybatis中的缓存机制
  8. &lt;每日一题&gt;题目22:简单的python练习题(31-40)
  9. css3之文本text-overflow 与 word-wrap, word-break
  10. linux删除登录日志及历史命令