GOJ1150（矩阵快速幂）

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 100010

using namespace std;

struct matrix

{

    LL m[][];

}ans;

matrix mult(matrix a,matrix b)

{

    matrix c;

    memset(c.m,,sizeof(c.m));

    for(int i=;i<;i++)

    for(int k=;k<;k++)

    {

        if(a.m[i][k]==)continue;

        for(int j=;j<;j++)

        {

            if(b.m[k][j]==)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,,sizeof(temp.m));

    for(int i=;i<;i++)temp.m[i][i]=;

    while(n)

    {

        if(n&)temp=mult(temp,x);

        x=mult(x,x);

        n>>=;

    }

    return temp;

}

LL fact(LL x)

{

    LL res=;

    for(int i=;i<=x;i++)res*=;

    return res;

}

int main()

{

    LL n,a;

    while(scanf("%lld%lld",&a,&n)!=EOF)

    {

        LL temp=a,len=;

        while(temp)

        {

            len++;

            temp/=;

        }

        LL p=fact(len);

        ans.m[][]=;ans.m[][]=;ans.m[][]=;

        ans.m[][]=p;ans.m[][]=p;ans.m[][]=;

        ans.m[][]=a;ans.m[][]=a;ans.m[][]=;

        ans=quickmod(ans,n-);

        LL res=ans.m[][]*a%mod+ans.m[][]*a%mod+ans.m[][];

        printf("%lld\n",res%mod);

    }

}