Sequence（矩阵快速幂变形）2018多校第七场

本文主要是介绍Sequence（矩阵快速幂变形）2018多校第七场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

题意一目了然，中间会改变的矩阵快速幂。

很显然，我并没有做过这种题，只做过中间不会改变的矩阵快速幂。

于是看题解发现我可以在矩阵中多加一个维度来储存每次加上的一个数，开一个三维矩阵。

| d c  [p/i] |        | f(n-1) |

| 1 0    0   |   *   | f(n-2) |

| 0 0    1   |        |     1   |

 

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a,b,c,d,p,n;struct mart
{int m[4][4];mart(){memset(m,0,sizeof(m));}
}ini;mart operator * (mart a,mart b)
{mart ans;for(int i=1;i<=3;i++)for(int j=1;j<=3;j++){long long t=0;for(int k=1;k<=3;k++)t+=(long long)a.m[i][k]*b.m[k][j];ans.m[i][j]=t%mod;}return ans;
}mart pow(mart a,int b)
{mart ans=ini;while(b){if(b&1)ans=a*ans;a=a*a;b>>=1;}return ans;
}void solve()
{scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&p,&n);if(n==1)    {printf("%d\n",a);return;}mart base;base.m[1][1]=d;base.m[1][2]=c;base.m[2][1]=1;base.m[3][3]=1;for(int i=3;i<=n;){if(p/i==0){long long ans;base=pow(base,n-i+1);ans=base.m[1][1]*(long long)b+base.m[1][2]*(long long)a+base.m[1][3];ans%=mod;printf("%d\n",ans);return;}int j=min(n,p/(p/i));mart tbase=base;tbase.m[1][3]=p/i;tbase=pow(tbase,j-i+1);long long A=tbase.m[2][1]*(long long)b+tbase.m[2][2]*(long long)a+tbase.m[2][3];long long B=tbase.m[1][1]*(long long)b+tbase.m[1][2]*(long long)a+tbase.m[1][3];a=A%mod;b=B%mod;i=j+1;}printf("%d\n",b);
}int main()
{ini.m[1][1]=ini.m[2][2]=ini.m[3][3]=1;int num;scanf("%d",&num);while(num--)solve();return 0;
}

 

这篇关于Sequence（矩阵快速幂变形）2018多校第七场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---