Description
假设$fib(n)$为斐波那契数列的第 $n$ 项，其中$fib(0)=0,fib(1)=1$，且$fib(n)=fib(n-1)+fib(n-2),(n > 1)$。 假设$S$是一个可重集合$\{ s_1,s_2,\cdots ,a_{|S|}$，$f(S)$ 定义为$f(S)=\sum_{T \subseteq S}[fib(\sum_{s \in T}s)]$ 有一个数组$a_1,a_2, \cdots ,a_n$，牛妹会对数组进行$q$次操作，每次操作可能是以下两种 操作中的一种： 1. 把$a_p$变为$v$； 2. 计算 $\sum_{i=l}^r \sum_{j=i}^r f(\{ a_i,a_{i+1},\cdots,a_j)\})$。 对于每个操作 2，输出答案模 $998244353$。
Solution
题目要求求出下式的值并支持修改操作：
$$\sum_{i=l}^r \sum_{j=i}^r f( \{a_i,a_{i+1}, \cdots ,a_j \})$$
其中$f(S)=\sum_{T \subseteq S}[fib(\sum_{s \in T}s)]$
设$g(n)=fib^2(n)$也可以递推，递推公式为$g(n)=2g(n-1)+2g(n-2)-g(n-3)$（证明方法：使用通项公式硬算）
可以用矩阵写出：
$$\begin{pmatrix}
g(n)\\
g(n-1)\\
g(n-2)
\end{pmatrix}
=
\begin{pmatrix}
2 & 2 & -1\\
1 & 0 & 0\\
0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
g(n-1) \\
g(n-2) \\
g(n-3)
\end{pmatrix}$$
然后换成向量：
$$\vec{g_n}=A\vec{g_{n-1}}=A^n\vec{g_0}$$
那么$\vec{f(S)}=\sum_{T \subseteq S}\vec{g_{\sum T}}$
考虑向$S$中加入一个数$a$，可以得到$\vec{f(S \cup \{a\})} = \vec{f(S)} + \sum_{T \subseteq S}\vec{g_{\sum T +a}} = \vec{f(S)} + A^a \vec{g_{\sum T}} = (A^a + 1) \vec{f(S)}$
$1$表示单位矩阵
设$S=\{a_1,a_2, \cdots ,a_n \}$，那么$\vec{f(S)}= \prod_{i=1}^n (1+A^{a_i})\vec{g_0}$
设$B_i=1+A^{a_i}$，那么题中所求即为$\sum_{i=l}^r \sum_{j=i}^r \prod_{k=i}^j B_k$
用线段树维护即可
常数特别难卡
#pragma GCC optimize(2)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,q;
const long long mod=998244353;
struct Matrix
{
int a[3][3];
inline void clear()
{
memset(a,0,sizeof(a));
}
Matrix operator + (Matrix z)const
{
for(register int i=0;i<3;i++) for(register int j=0;j<3;j++) (z.a[i][j]+=this->a[i][j])<mod?0:z.a[i][j]-=mod;
return z;
}
Matrix operator * (const Matrix &z)const
{
return (Matrix){
(a[0][0]*1ll*z.a[0][0]+a[0][1]*1ll*z.a[1][0]+a[0][2]*1ll*z.a[2][0])%mod,
(a[0][0]*1ll*z.a[0][1]+a[0][1]*1ll*z.a[1][1]+a[0][2]*1ll*z.a[2][1])%mod,
(a[0][0]*1ll*z.a[0][2]+a[0][1]*1ll*z.a[1][2]+a[0][2]*1ll*z.a[2][2])%mod,
(a[1][0]*1ll*z.a[0][0]+a[1][1]*1ll*z.a[1][0]+a[1][2]*1ll*z.a[2][0])%mod,
(a[1][0]*1ll*z.a[0][1]+a[1][1]*1ll*z.a[1][1]+a[1][2]*1ll*z.a[2][1])%mod,
(a[1][0]*1ll*z.a[0][2]+a[1][1]*1ll*z.a[1][2]+a[1][2]*1ll*z.a[2][2])%mod,
(a[2][0]*1ll*z.a[0][0]+a[2][1]*1ll*z.a[1][0]+a[2][2]*1ll*z.a[2][0])%mod,
(a[2][0]*1ll*z.a[0][1]+a[2][1]*1ll*z.a[1][1]+a[2][2]*1ll*z.a[2][1])%mod,
(a[2][0]*1ll*z.a[0][2]+a[2][1]*1ll*z.a[1][2]+a[2][2]*1ll*z.a[2][2])%mod
};
}
Matrix operator ^ (int z)const
{
Matrix ret,base;
ret.clear();
ret.a[0][0]=ret.a[1][1]=ret.a[2][2]=1;
base=*this;
while(z)
{
if(z&1) ret=ret*base;
z>>=1;
base=base*base;
}
return ret;
}
}M[100005],I,O,A;
struct Tree
{
Matrix S,L,R,V;
Tree operator + (Tree z)const
{
return (Tree){S+z.S+R*z.L,L+V*z.L,z.R+z.V*R,V*z.V};
}
}tree[400005];
inline int read()
{
int w=0;
char ch=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
return w;
}
void update(int i,int l,int r,int pos)
{
if(l==r)
{
tree[i].S=tree[i].L=tree[i].R=tree[i].V=M[l];return;
}
int mid=l+r>>1;
if(pos<=mid) update(i<<1,l,mid,pos);
else update(i<<1|1,mid+1,r,pos);
tree[i]=tree[i<<1]+tree[i<<1|1];
}
Tree query(int i,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr) return tree[i];
int mid=l+r>>1;
if(rr<=mid) return query(i<<1,l,mid,ll,rr);
else if(ll>mid) return query(i<<1|1,mid+1,r,ll,rr);
else return query(i<<1,l,mid,ll,rr)+query(i<<1|1,mid+1,r,ll,rr);
}
int main()
{
I.a[0][0]=I.a[1][1]=I.a[2][2]=1;
O.a[1][0]=O.a[2][0]=1;
A.a[0][0]=A.a[0][1]=2,A.a[0][2]=mod-1,A.a[1][0]=A.a[2][1]=1;
n=read(),q=read();
for(register int i=1;i<=n;i++) M[i]=(A^read())+I,update(1,1,n,i);
for(register int i=1;i<=q;i++)
{
int opt=read();
if(opt==1)
{
int p=read(),v=read();
M[p]=(A^v)+I,update(1,1,n,p);
}
else
{
int l=read(),r=read();
printf("%d\n",((query(1,1,n,l,r).S*O).a[0][0]+mod)%mod);
}
}
return 0;
}
斐波