题解：P16389 [IATI 2024] Five
lailai0916
·
·
题解
题意简述
一个五阶线性递推数列的下标可以为任意整数。维护整数数组 a 的区间加法，并查询区间内 x_{a_i} 的和，答案对 M=10^8+543 取模。
解题思路
递推的特征多项式为：
P(t)=t^5-5t^4-4t^3-3t^2-2t-1
| $j$ | $r_j$ | $c_j$ |
| :-: | :-: | :-: |
| $0$ | $82181655$ | $13944628$ |
| $1$ | $69727867$ | $37815043$ |
| $2$ | $36684046$ | $51211683$ |
| $3$ | $10002474$ | $92161528$ |
| $4$ | $1405049$ | $4868204$ |
这些常数满足：
$$
P(t)\equiv\prod_{j=0}^4(t-r_j)\pmod M
$$
对每个 $0\le k\le4$，还满足：
$$
\sum_{j=0}^4c_jr_j^k\equiv k\pmod M
$$
逐个枚举模 $M$ 的元素并代入 $P$，可以得到这张根表。再对初值建立五元线性方程组，即可求出系数。实现中直接保存这组常数。上述两个等式提供了可独立复核的判据。
每个 $r_j^k$ 都满足原递推，线性组合仍满足递推。第二个等式说明该组合与 $x_k$ 的前 $5$ 项相同，所以递推唯一性给出：
$$
x_k\equiv\sum_{j=0}^4c_jr_j^k\pmod M
$$
这个结论同样覆盖负下标。原递推中 $x_k$ 的系数为 $1$，已知连续后 $5$ 项时可以唯一反推出 $x_k$。另一方面，所有 $r_j$ 均非零，所以 $r_j^k$ 对负整数 $k$ 也有定义。两侧是同一个双向递推的解。
由费马小定理，非零底数满足 $r_j^{M-1}\equiv1\pmod M$。计算 $r_j^k$ 时，先把任意正负指数 $k$ 归一化到 $[0,M-2]$ 即可。
线段树结点对每个 $0\le j<5$ 维护：
$$
f_j=\sum_{i=l}^rr_j^{a_i}\pmod M
$$
若区间内所有 $a_i$ 增加 $d$，则对应分量满足：
$$
f_j\gets r_j^df_j
$$
因此，懒标记保存 $5$ 个乘数，并按分量相乘。查询区间得到全部 $f_j$ 后，答案为：
$$
\sum_{j=0}^4c_jf_j\pmod M
$$
若每次计算 $r_j^d$ 都使用快速幂，单次修改还会多一个对数。取 $B=10000$，把规范化后的指数写为 $d=uB+v$。预处理 $r_j^v$ 与 $(r_j^B)^u$ 后，一次乘法即可得到 $r_j^d$。
预处理和建树的时间复杂度为 $O(n+\sqrt{M})$。每次操作的时间复杂度为 $O(\log n)$，空间复杂度为 $O(n+\sqrt{M})$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100005;
const int M=400005;
const int B=10000;
const int K=10005;
const int mod=100000543;
const int r[5]={82181655,69727867,36684046,10002474,1405049};
const int c[5]={13944628,37815043,51211683,92161528,4868204};
int a[N],sm[5][B],bg[5][K];
ll Pow(ll x,ll y)
{
x%=mod;
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void init()
{
for(int i=0;i<5;i++)
{
sm[i][0]=1;
for(int j=1;j<B;j++)sm[i][j]=(ll)sm[i][j-1]*r[i]%mod;
bg[i][0]=1;
int x=Pow(r[i],B);
for(int j=1;j<K;j++)bg[i][j]=(ll)bg[i][j-1]*x%mod;
}
}
int power(int i,ll x)
{
x%=mod-1;
if(x<0)x+=mod-1;
int p=x/B,q=x%B;
return (ll)bg[i][p]*sm[i][q]%mod;
}
struct SEG
{
int val[M][5],tag[M][5];
bool vis[M];
void gx(int u,const int p[])
{
for(int i=0;i<5;i++)
{
val[u][i]=(ll)val[u][i]*p[i]%mod;
tag[u][i]=(ll)tag[u][i]*p[i]%mod;
}
vis[u]=1;
}
void push_up(int u)
{
for(int i=0;i<5;i++)val[u][i]=(val[u*2][i]+val[u*2+1][i])%mod;
}
void push_down(int u)
{
if(!vis[u])return;
gx(u*2,tag[u]);
gx(u*2+1,tag[u]);
for(int i=0;i<5;i++)tag[u][i]=1;
vis[u]=0;
}
void build(int u,int l,int r)
{
for(int i=0;i<5;i++)tag[u][i]=1;
vis[u]=0;
if(l==r)
{
for(int i=0;i<5;i++)val[u][i]=power(i,a[l]);
return;
}
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int x,int y,const int p[])
{
if(x<=l&&r<=y){gx(u,p);return;}
push_down(u);
int mid=l+r>>1;
if(x<=mid)update(u*2,l,mid,x,y,p);
if(y>mid)update(u*2+1,mid+1,r,x,y,p);
push_up(u);
}
void query(int u,int l,int r,int x,int y,int res[])
{
if(x<=l&&r<=y)
{
for(int i=0;i<5;i++)res[i]=(res[i]+val[u][i])%mod;
return;
}
push_down(u);
int mid=l+r>>1;
if(x<=mid)query(u*2,l,mid,x,y,res);
if(y>mid)query(u*2+1,mid+1,r,x,y,res);
}
}T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
T.build(1,1,n);
while(q--)
{
int op,l,r;
cin>>op>>l>>r;
if(op==1)
{
int res[5]={};
T.query(1,1,n,l,r,res);
ll ans=0;
for(int i=0;i<5;i++)ans=(ans+(ll)c[i]*res[i])%mod;
cout<<ans<<'\n';
}
else if(op==2)
{
int x;
cin>>x;
int p[5];
for(int i=0;i<5;i++)p[i]=power(i,x);
T.update(1,1,n,l,r,p);
}
}
return 0;
}
```