Bubble Cup 8 - Finals [Online Mirror] - A.Fibonotci【分段+ST表】

快来打我* 2022-08-04 15:58 44阅读 0赞

因为 si为近似周期序列，而且告诉你了m个位置以及数字。  
那么就将序列分成m段，每一段用一个ST表来维护区间矩阵乘积  
然后注意一些细节，比如m<script type="math/tex" id="MathJax-Element-259">m</script>段分段如果两个不周期位置连续，以及最后一个段等等。

想法还是比价明显的，但是确实不好写….

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=50005;
    int MOD;
    struct Matrix {
        int Data[2][2];
    };
    Matrix operator*(Matrix a,Matrix b)
    {
        Matrix c;
        memset(c.Data,0,sizeof(c.Data));
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                for(int k=0;k<2;k++) {
                    c.Data[i][j]+=(long long)a.Data[i][k]*b.Data[k][j]%MOD;
                    c.Data[i][j]%=MOD;
                }
            }
        }
        return c;
    }
    int a[MAXN];
    pair<long long,int>P[MAXN];
    Matrix ST[MAXN][63];
    int n;
    Matrix query(long long l,long long len)
    {
        int pos=l%n;
        Matrix ans;
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                ans.Data[i][j]=i==j?1:0;
            }
        }
        for(int i=0;i<63;i++) {
            if(len&(1LL<<i)) {
                ans=ans*ST[pos][i];
                pos=(pos+(1LL<<i)%n)%n;
            }
        }
        return ans;
    }
    int main()
    {
        //freopen("a.txt","r",stdin);
        long long k;
        while(~scanf("%I64d%d%d",&k,&MOD,&n)) {
            for(int i=0;i<n;i++) {
                scanf("%d",&a[i]);
            }
            int m;
            scanf("%d",&m);
            for(int i=0;i<m;i++) {
                scanf("%I64d%d",&P[i].first,&P[i].second);
            }
            sort(P,P+m);
            for(int i=0;i<n;i++) {
                ST[i][0].Data[0][0]=a[(i-1+n)%n];
                ST[i][0].Data[1][0]=a[(i-2+n)%n];
                ST[i][0].Data[0][1]=1;
                ST[i][0].Data[1][1]=0;
            }
            for(int j=1;j<63;j++) {
                for(int i=0;i<n;i++) {
                    ST[i][j]=ST[i][j-1]*ST[(i+(1LL<<(j-1))%n)%n][j-1];
                }
            }
            Matrix S;
            S.Data[0][0]=1;
            S.Data[0][1]=0;
            if(k==0) {
                printf("0\n");
                continue;
            }
            if(k==1) {
                printf("%d\n",1%MOD);
                continue;
            }
            long long l=1;
            for(int i=0;i<m;i++) {
                long long r=P[i].first;
                if(r>=k)  break;
                S=S*query(l+1,r-l);
                l=r;
                //printf("%d-%d %d\n",l,S.Data[0][0],S.Data[0][1]);
                if(l>=k)  break;
    
                Matrix tmp;
                tmp.Data[0][0]=P[i].second;
                tmp.Data[1][0]=(i==0||P[i-1].first+1!=P[i].first)?a[(r-1+n)%n]:P[i-1].second;
                tmp.Data[0][1]=1;
                tmp.Data[1][1]=0;
                S=S*tmp;
                l=r+1;
                //printf("%d--%d %d %d %d\n",l,S.Data[0][0],S.Data[0][1],tmp.Data[0][0],tmp.Data[1][0]);
                if(l>=k)  break;
    
                if(i==m-1||P[i].first+1!=P[i+1].first) {
                    tmp.Data[0][0]=a[(r+1)%n];
                    tmp.Data[1][0]=P[i].second;
                    tmp.Data[0][1]=1;
                    tmp.Data[1][1]=0;
                    S=S*tmp;
                    l=r+2;
                    //printf("%d---%d %d\n",l,S.Data[0][0],S.Data[0][1]);
                    if(l>=k)  break;
                }
            }
            S=S*query(l+1,k-l);
            printf("%d\n",S.Data[0][0]);
        }
        return 0;
    }