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

本文主要是介绍Bubble Cup 8 - Finals [Online Mirror] - A.Fibonotci【分段+ST表】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为 $s_i$ 为近似周期序列，而且告诉你了 $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;
}