CF575A Fibonotci(线段树维护矩阵乘法)

木xx木大 · 2020-10-28 16:46:04 · 题解

CF575A Fibonotci

这是一道动态dp递推

看到近似Fibonacci的递推，我们想到矩阵乘法，朴素递推式为

如果没有修改，我们可以暴力算出每个循环节内的答案，用矩阵快速幂求总答案。而修改最多只会涉及 m 个循环节，复杂度 O(nm)。

考虑优化：在原矩阵乘积的基础上进行修改。注意到一个 s_i 的改变只会影响两个区间，那么我们需要单点修改，全局查询，用线段树维护即可。对于一个有特殊点的周期，我们先修改，算完再改回去即可。

实现时的小技巧：一个 s_i 的改变涉及两个转移矩阵的改变，那么我们可以把一个修改拆成两个，这样可以避免很多特判。

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
using namespace std;
namespace FGF
{
    int n,m;
    const int N=5e4+5;
    struct matrx{
        ll a[2][2];
    }t[N<<2],ans,c[N],b[N];
    struct Node{
        ll pos,w;
        int op;
    }q[N<<1];
    ll K,p;
    int a[N];
    matrx operator *(matrx x,matrx y)
    {
        matrx s;
        memset(s.a,0,sizeof(s.a));
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    s.a[i][j]=(s.a[i][j]+x.a[i][k]*y.a[k][j]%p)%p;
        return s;
    }
    void build(int ro,int l,int r)
    {
        if(l==r)
        {
            c[l].a[0][1]=a[l-1],c[l].a[1][0]=1,c[l].a[1][1]=a[l%n];
            b[l]=t[ro]=c[l];
            return; 
        }
        build(ro<<1,l,mid),build(ro<<1|1,mid+1,r);
        t[ro]=t[ro<<1]*t[ro<<1|1];
    }
    void updat(int ro,int l,int r,int pos)
    {
        if(l==r)
        {
            t[ro]=b[pos];
            return; 
        }
        pos<=mid? updat(ro<<1,l,mid,pos):updat(ro<<1|1,mid+1,r,pos);
        t[ro]=t[ro<<1]*t[ro<<1|1];
    }
    matrx qpow(matrx x,ll y)
    {
        matrx s;s.a[0][0]=s.a[1][1]=1,s.a[0][1]=s.a[1][0]=0;
        while(y)
        {
            if(y&1)s=s*x;
            x=x*x;
            y>>=1;
        }
        return s;
    }
    bool cmp(Node x,Node y)
    {
        return x.pos<y.pos;
    }
    void work()
    {
        scanf("%lld%lld",&K,&p);
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]),a[i]%=p;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld",&q[i].pos,&q[i].w),q[i].w%=p;
            q[i].op=1,q[i+m].pos=q[i].pos+1,q[i+m].w=q[i].w;
        }
        m<<=1;
        sort(q+1,q+m+1,cmp);
        while(m&&q[m].pos>K)m--;
        build(1,1,n);
        ans.a[0][0]=0,ans.a[0][1]=1;
        ll lst=0;
        for(int i=1,j=1;i<=m;i=++j)
        {
            ll now=(q[i].pos-1)/n;
            while(j<m&&(q[j+1].pos-1)/n==now)++j;
            ans=ans*qpow(t[1],now-lst);
            lst=now;
            for(int k=i;k<=j;k++)
            {
                int pos=(q[k].pos-1)%n+1;
                b[pos].a[q[k].op][1]=q[k].w;
                updat(1,1,n,pos);
            }
            if(now==K/n)break;
            ans=ans*t[1],lst=now+1;
            for(int k=i;k<=j;k++)
            {
                int pos=(q[k].pos-1)%n+1;
                b[pos]=c[pos];
                updat(1,1,n,pos);
            }
        }
        ll now=K/n;
        ans=ans*qpow(t[1],now-lst);
        for(int i=1,d=K%n;i<=d;i++)
            ans=ans*b[i];
        printf("%lld",ans.a[0][0]);
    }
}
int main()
{
    FGF::work();
    return 0;
}