首页 > 代码库 > GOJ1150（矩阵快速幂）

GOJ1150（矩阵快速幂）

2024-08-05 10:45:31   217人阅读

sum

Time Limit: 1000ms

Problem Description:

 给定a和n，计算a+aa+aaa+aaaa+...+a...a(n个a) 的和。

Input:

测试数据有多组,以文件结尾。每行输入a，n（1<=a<=10^9,1=<n<=10^18）。

Output:

由于结果可能比较大，所以请输出答案mod 1000000007。

Sample Input:

3 2

Sample Output:

36


分析：数列a，aa，aaa...符合公式f[n]=pow(10,len)+a(len为a的位数);则g[n]=g[n-1]+f[n];
由上面两个公式可构造矩阵:
                                |1,0,0|
|g[n],f[n],1|=|g[n-1],f[n-1],0|*|p,p,0|(其中p=pow(len,10))
                                |a,a,1|

递推得|g[n],f[n],1|=|g[1],f[1],0,|*ans^(n-1);ans为构造矩阵f[1]=g[1]=a;

所以最终答案为res=a*ans.m[0][0]+a*ans.m[0][1]+ans.m[0][2]

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007#define N 100010using namespace std;struct matrix{    LL m[3][3];}ans;matrix mult(matrix a,matrix b){    matrix c;    memset(c.m,0,sizeof(c.m));    for(int i=0;i<3;i++)    for(int k=0;k<3;k++)    {        if(a.m[i][k]==0)continue;        for(int j=0;j<3;j++)        {            if(b.m[k][j]==0)continue;            c.m[i][j]+=(a.m[i][k]%mod)*(b.m[k][j]%mod)%mod;            c.m[i][j]%=mod;        }    }    return c;}matrix quickmod(matrix x,LL n){    matrix temp;    memset(temp.m,0,sizeof(temp.m));    for(int i=0;i<3;i++)temp.m[i][i]=1;    while(n)    {        if(n&1)temp=mult(temp,x);        x=mult(x,x);        n>>=1;    }    return temp;}LL fact(LL x){    LL res=1;    for(int i=1;i<=x;i++)res*=10;    return res;}int main(){    LL n,a;    while(scanf("%lld%lld",&a,&n)!=EOF)    {        LL temp=a,len=0;        while(temp)        {            len++;            temp/=10;        }        LL p=fact(len);        ans.m[0][0]=1;ans.m[0][1]=0;ans.m[0][2]=0;        ans.m[1][0]=p;ans.m[1][1]=p;ans.m[1][2]=0;        ans.m[2][0]=a;ans.m[2][1]=a;ans.m[2][2]=1;        ans=quickmod(ans,n-1);        LL res=ans.m[0][0]*a%mod+ans.m[1][0]*a%mod+ans.m[2][0];        printf("%lld\n",res%mod);    }}
View Code

 




 

GOJ1150（矩阵快速幂）


联系
我们