题解：B3646 数列前缀和 3

Redamancy_Lydic · 2024-07-16 20:02:28 · 题解

背景

没有人写线段树？那我来写一发。

前置

矩阵乘法，单位元矩阵，线段树。

分析

这道题目给了我们一些矩阵，让我们多次求出一个给定区间内所有矩阵的乘积。

这道题当然可以直接用矩阵前缀积来做，但是因为要取模，所以需要求出矩阵逆，这样问题就变得复杂了。怎么办呢？线段树！

我们在线段树的每个叶子节点上面存一个矩阵，其余的存储区间矩阵积。最开始把所有的矩阵存进去，然后每次查询的时候按照题目要求异或即可。

需要注意的是，线段树查询操作累乘答案的时候，答案的初值应为单位元矩阵，否则会影响答案。

其余的就是一些常见的小细节了，放代码。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int maxn=1e6+10;
const int mod=1145141;
int n,Q,ans=0,k;
struct no
{
    int num[4][4];
    int* operator [] (int i) 
    {
        return num[i]; 
    }
    no()
    {
        memset(num,0,sizeof num);
        for(int i=1;i<=k;i++)
        {
            num[i][i]=1;
        }
    }
    inline void _read()
    {
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                num[i][j]=read();
            }
        }
    }
    inline void clear()
    {
        memset(num,0,sizeof num);
    }
    inline friend no operator * (no aa,no b)
    {
        no c;
        c.clear();
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                for(int q=1;q<=k;q++)
                {
                    c[i][j]=(c[i][j]+aa[i][q]*b[q][j]%mod)%mod;
                }
            }
        }
        return c;
    }
    inline int xor_()
    {
        int res=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                res=res^num[i][j];
            }
        }
        return res;
    }
}a[maxn];
struct Segment_Tree
{
    int l,r;
    no d;
}t[2001000];
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
        t[p].d=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].d=t[p*2].d*t[p*2+1].d;
}
no ask(int p,int l,int r)
{
    if(t[p].l>=l&&t[p].r<=r)return t[p].d;
    int mid=(t[p].l+t[p].r)>>1;
    no ans;
    if(mid>=l)ans=ans*ask(p*2,l,r);
    if(mid<r)ans=ans*ask(p*2+1,l,r);
    return ans;
}
signed main()
{
    cin>>n>>k>>Q;
    for(int i=1;i<=n;i++)
    {
        a[i]._read();
    }
    build(1,1,n);
    while(Q--)
    {
        int l=read(),r=read();
        no z=ask(1,l,r);
        ans=ans^z.xor_();
    }
    cout<<ans;
    return 0;
}