2019牛客暑期多校训练营（第五场）B-generator 1(矩阵快速幂的小技巧)

a矩阵的123次幂是不是可以拆成：$a^{120}\ast a^3$，$a^{12}$是不是可以拆成$a^{10}\ast a^2$，于是当我们面对一个超级大的次幂，例如长度为1e6的字符串次幂，我们可以预处理矩阵的0~9次幂出来，然后从前向后计算：(就相当于字符串转成十进制数字时候的模拟过程)

	int k;
char s[1000009];
for(int i=0;i<len;++i){
res=quick(res,10);
k=s[i]-'0';
res=res*a[k];
}

那么这个的复杂度显然为：$O(len\ast lo{g}_2(10)\ast n^3)$
其中n为矩阵大小，len为字符串长度，log10为快速幂的操作。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
char s[maxn];
int mod;
struct Node{
ll a[2][2];
Node operator * (Node b){
Node res;
res.a[0][0]=res.a[1][1]=res.a[0][1]=res.a[1][0]=0;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;
return res;
}
}danwei,yuanshi[19],temp;
Node quick(Node a,int b){
temp.a[0][0]=temp.a[1][1]=1;
temp.a[0][1]=temp.a[1][0]=0;
while(b){
if(b&1) temp=temp*a;
a=a*a;
b>>=1;
}
return temp;
}
int main(){
int x0,x1,a,b;
scanf("%d%d%d%d%s%d",&x0,&x1,&a,&b,s,&mod);
danwei.a[0][0]=danwei.a[1][1]=1;
yuanshi[0].a[0][0]=yuanshi[0].a[1][1]=1;
yuanshi[0].a[0][1]=yuanshi[0].a[1][0]=0;
yuanshi[1].a[0][0]=a,yuanshi[1].a[0][1]=b;
yuanshi[1].a[1][0]=1,yuanshi[1].a[1][1]=0;
for(int i=2;i<=9;++i)
yuanshi[i]=yuanshi[i-1]*yuanshi[1];
int len=strlen(s);
int k;
for(int i=0;i<len;++i){
danwei=quick(danwei,10);
k=s[i]-'0';
danwei=danwei*yuanshi[k];
}
printf("%lldn",(danwei.a[1][0]*x1+danwei.a[1][1]*x0)%mod);
return 0;
}

最后

以上就是儒雅高跟鞋为你收集整理的2019牛客暑期多校训练营（第五场）B-generator 1(矩阵快速幂的小技巧)的全部内容，希望文章能够帮你解决2019牛客暑期多校训练营（第五场）B-generator 1(矩阵快速幂的小技巧)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。