矩阵线段树
发布日期:2022-02-22 18:04:17 浏览次数:14 分类:技术文章

本文共 2595 字,大约阅读时间需要 8 分钟。

线段树维护矩阵

无标题.png

直接维护矩阵

摒弃之前难看的代码,换上清真的

#include
using namespace std;using LL = long long;template
T mian(){ T s=0,f=1;char ch; while(!isdigit(ch=getchar()))(ch=='-')&&(f=-1); for(s=ch-'0';isdigit(ch=getchar());s=s*10+ch-'0'); return s*f;}const int maxn = 5e5+5;const int p = 1e9+7;struct Matrix{ LL c[2][2]; Matrix(){clear();} void clear(){memset(c,0,sizeof(c));} void e(){clear();c[0][0]=c[1][1]=1;} LL *operator[](int x){return c[x];} const LL*operator[](int x)const{return c[x];} friend Matrix operator*(const Matrix &a,const Matrix &b){ Matrix ans; ans[0][0]=(a[0][0]*b[0][0]%p+a[0][1]*b[1][0]%p)%p; ans[0][1]=(a[0][0]*b[0][1]%p+a[0][1]*b[1][1]%p)%p; ans[1][0]=(a[1][0]*b[0][0]%p+a[1][1]*b[1][0]%p)%p; ans[1][1]=(a[1][0]*b[0][1]%p+a[1][1]*b[1][1]%p)%p; return ans; } friend Matrix operator + (const Matrix &a,const Matrix &b){ Matrix ans; ans[0][0]=(a[0][0]+b[0][0])%p; ans[0][1]=(a[0][1]+b[0][1])%p; ans[1][0]=(a[1][0]+b[1][0])%p; ans[1][1]=(a[1][1]+b[1][1])%p; return ans; }}base;Matrix ksm(Matrix b,int n){ Matrix ans;ans.e(); for(;n;n>>=1,b=b*b) if(n&1)ans=ans*b; return ans;}struct Seg_Node{ Seg_Node *lch,*rch; int l,r,isfucked; Matrix sum,add; Seg_Node():lch(NULL),rch(NULL),l(0),r(0),isfucked(0){} int mid(){return (l+r)>>1;} void push_up(){ sum=lch->sum+rch->sum; } void plus(Matrix x){sum=x*sum;add=x*add;isfucked=1;} void push_down(){ if(!isfucked)return ; lch->plus(add); rch->plus(add); add.e(); isfucked=0; } };typedef Seg_Node* ptr;ptr root;void build(int l,int r,ptr &o=root){ //printf("%d %d\n",l,r); o=new Seg_Node; o->l=l; o->r=r; o->add.e(); o->isfucked=0; if(l==r)return (void)(o->sum=ksm(base,mian()-1)); int mid=o->mid(); build(l,mid,o->lch); build(mid+1,r,o->rch); o->push_up();}void addval(int l,int r,Matrix val,ptr o=root){ if(l<=o->l&&o->r<=r)return o->plus(val); int mid=o->mid(); o->push_down(); if(l<=mid)addval(l,r,val,o->lch); if(r>mid) addval(l,r,val,o->rch); o->push_up();}LL getsum(int l,int r,ptr o=root){ if(l<=o->l&&o->r<=r)return o->sum[0][0]; int mid=o->mid();LL ans=0; o->push_down(); if(l<=mid)(ans+=getsum(l,r,o->lch))%=p; if(r>mid) (ans+=getsum(l,r,o->rch))%=p; return ans;}int n,m;int main(){ base[0][0]=base[0][1]=base[1][0]=1; base[1][1]=0; n=mian(),m=mian(); build(1,n); for(int i=0;i

转载于:https://www.cnblogs.com/eric-walker/p/10273106.html

转载地址:https://blog.csdn.net/dengxingrao0615/article/details/102231371 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:关于VUE中 import 、 export 和 export default 的注意问题
下一篇:[SCOI2005]互不侵犯

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月12日 21时33分09秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux指定用户执行crontab,Centos下crontab 指定执行用户 2019-04-21
linux 截屏函数,使用imlib2函数库实现截屏功能 2019-04-21
linux 管理桌面图标,使用GNOME优化工具自定义Linux桌面的10种方法 2019-04-21
linux clone命令,git clone命令 2019-04-21
linux拷贝账户到mnt,linux基础与应用 -电脑资料 2019-04-21
linux安装更换yum源,CentOS 7更换yum源 2019-04-21
arm linux 文件 分组,ARM Linux根文件系统制作 2019-04-21
linux让系统再下午三点关机的命令,Linux的关机命令 2019-04-21
linux mint下安装vnc,如何在Linux Mint 20上安装VNC服务器 2019-04-21
i7 安装 linux,关于新手安装Ubuntu系统 2019-04-21
单片机c语言按键中断程序,单片机C语言代码:外部中断,按下中断按键LED不亮,LED1正常亮... 2019-04-21
c语言自定义scopy,C++自定义复制构造函数详解 2019-04-21
c语言 宏定义 64位变量,【图片】初试64位宏汇编(努力构造了一个“invoke”宏)_汇编吧_百度贴吧... 2019-04-21
标识符可以由汉字组成 c语言,C语言程序设计考题 2019-04-21
c语言中图像,C语言图像函数 2019-04-21
台式电脑w ndows7密钥,windows7品牌机各版本oem密钥 2019-04-21
抛物型方程的有限差分 C语言程序,抛物型方程有限差分方法的应用 - 报告.doc 2019-04-21
freemarker将xml转为html,Spring Boot与FreeMarker集成后配置全局模板转义html/xml 2019-04-21
shp设置utf8格式_shp文件格式说明 2019-04-21
c++ gdi 图片上绘制文字_电脑上如何提取图片中的文字?教你3个方法,10秒轻松搞定... 2019-04-21