【Codeforces 575A】Fibonotci | Mrsrz's blog

线段树，矩阵快速幂。

题目大意：

给定一个无限长的数列 $s$，给出前 $n$ 项 $s_0,s_1,\ldots,s_{n-1}$。之后的项满足 $s_i=s_{i\bmod n}$。

再给出一个无限长的数列 $f$，$f_0=0,f_1=1$，对于 $i\geq 2$，$f_i=s_{i-1}f_{i-1}+s_{i-2}f_{i-2}$。

现在有 $m$ 个位置的 $s$ 不满足 $s_i=s_{i\bmod n}$ 而是被钦定为了一个值。

求 $f_k$ 模 $p$ 的结果。

题解：

考虑不存在不满足循环条件的数时的做法。

这个数列显然可以用矩阵乘法进行转移。我们发现每 $n$ 个转移矩阵都是一样的，所以可以用乘法结合律合并，然后对 $n$ 个的乘积一起进行矩阵快速幂。最后一段不完整的可以直接暴力乘起来。时间复杂度 $O(n+\log k)$。

如果存在不满足循环条件的数，那么原数列相当于被分成了 $O(m)$ 个段，每段里我们可以用矩阵快速幂和暴力进行求值。然后依次相乘即可。这样的时间复杂度为 $O(nm+m\log k)$。

由于现在有 $m$ 个段，所以不完整的部分我们不能再暴力了。我们使用线段树维护区间乘积，然后不完整的段的乘积就可以 $O(\log n)$ 求得。

这样时间复杂度就是 $O(n+m(\log n+\log k))$。

Code：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=114514;
LL k;int md,n,s[N],m;
struct qwq{
    LL x;int v;
    inline bool operator<(const qwq&rhs)const{return x<rhs.x;}
}B[N];
struct mat{
    int A[2][2];
    inline int*operator[](const int&x){return A[x];}
    inline mat(){A[0][0]=A[0][1]=A[1][0]=A[1][1]=0;}
    inline mat(const int&a,const int&b,const int&c,const int&d){
        A[0][0]=a,A[0][1]=b,A[1][0]=c,A[1][1]=d;
    }
    inline mat operator*(const mat&b)const{
        mat c;
        c[0][0]=((LL)A[0][0]*b.A[0][0]+(LL)A[0][1]*b.A[1][0])%md;
        c[0][1]=((LL)A[0][0]*b.A[0][1]+(LL)A[0][1]*b.A[1][1])%md;
        c[1][0]=((LL)A[1][0]*b.A[0][0]+(LL)A[1][1]*b.A[1][0])%md;
        c[1][1]=((LL)A[1][0]*b.A[0][1]+(LL)A[1][1]*b.A[1][1])%md;
        return c;
    }
}d[N<<2],f;
vector<pair<LL,mat> >vec;
void build(int l,int r,int o){
    if(l==r)d[o]=mat(0,s[l-1],1,s[l]);else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=d[o<<1]*d[o<<1|1];
    }
}
void query(int l,int r,int o,const int&L,const int&R,mat&f){
    if(L<=l&&r<=R)f=f*d[o];else{
        const int mid=l+r>>1;
        if(L<=mid)query(l,mid,o<<1,L,R,f);
        if(mid<R)query(mid+1,r,o<<1|1,L,R,f);
    }
}
void pow(mat a,LL b,mat&f){
    for(;b;b>>=1,a=a*a)
    if(b&1)f=f*a;
}
int main(){
    scanf("%lld%d%d",&k,&md,&n);
    for(int i=0;i<n;++i)scanf("%d",s+i),s[i]%=md;
    s[n]=*s;
    f=mat(0,1,0,0);
    build(1,n,1);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)scanf("%lld%d",&B[i].x,&B[i].v),B[i].v%=md;
    sort(B+1,B+m+1);
    for(int i=1;i<=m;++i)if(B[i].x<=k){
        if(i==1||B[i].x!=B[i-1].x+1)
        vec.push_back(make_pair(B[i].x,mat(0,s[(B[i].x-1)%n],1,B[i].v)));else
        vec.back().second.A[1][1]=B[i].v;
        if(B[i].x+1<=k)
        vec.push_back(make_pair(B[i].x+1,mat(0,B[i].v,1,s[(B[i].x+1)%n])));
    }
    int it=0;
    for(LL nw=0;nw!=k;){
        LL nxt=(it==vec.size()?k:vec[it].first-1);
        if(nw/n!=nxt/n){
            int m=nw%n+1;
            query(1,n,1,m,n,f);
            nw=nw-(nw%n)+n;
            if(nw/n!=nxt/n)pow(d[1],nxt/n-nw/n,f),nw=nxt/n*n;
        }
        if(nxt%n)query(1,n,1,nw%n+1,nxt%n,f);
        nw=nxt;
        if(nw==k)break;
        f=f*vec[it++].second;
        ++nw;
    }
    printf("%d\n",f[0][0]);
    return 0;
}