等比数列是指从第二项起，每一项与它的前一项的比值等于同一个常数的一种数列。对于一个等比数列an=a1 * qn-1，它的前n项的和Sn=a1 * (1-qn)/(1-q)(q≠1)。现在已知A为n*n的矩阵，S=A+A2+A3+…+Am，你能否正确求出S，并且输出S中的每一个元素对1000000007取模后的值。

输入

输入包括n+1行，第一行包括两个正整数n, m，分别代表矩阵A的大小和S中的项数，其中1≤n≤30, 1≤m≤109。接下来n行，每行n个元素，相应地代表A中的元素x，其中0≤x≤106。

输出

输出包括n行，每行n个元素，相应地代表S中的每一个元素对1000000007取模后的值。

样例输入 Copy

1 2019
1

样例输出 Copy

2019

第一反应就是分治，因为等比可分治。
纪念lz学长，带老。
不过题解不是分治写的。
这里就都记一下啦，分治公式以后用到了自己推。。

分治写法：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#define ll long long
using namespace std;
const int maxn=35;
const int mod=1000000007;
struct node
{
    ll a[maxn][maxn];
}res;
 
int n,m;
 
node operator * (const node &a,const node &b)
{
    node c;
    memset(c.a,0,sizeof(c.a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            }
        }
    }
    return c;
}
 
node operator +(const node &a,const node &b)
{
    node c;
    memset(c.a,0,sizeof(c.a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
    }
    return c;
}
 
node mypow(node a,ll b)
{
    node ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=1;i<=n;i++)
        ans.a[i][i]=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
 
node getans(ll now)
{
    if(now==1)
        return res;
    node c=getans(now/2);
    if(now&1)
    {
        node d=mypow(res,now/2+1);
        node e=c*d+d+c;
        return e;
    }
    else return c*mypow(res,now/2)+c;
}
 
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&res.a[i][j]);
        }
    }
    node ans=getans(m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j!=1) putchar(' ');
            printf("%lld",ans.a[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

题解：
懒得写了，记录一下这种解法。