牛客小白月赛6-洋灰三角

时间限制

1000ms

空间限制

262144K

题目：

洋灰是一种建筑材料，常用来筑桥搭建高层建筑，又称，水泥、混凝土。

WHZ有很多铸造成三角形的洋灰块，他想把这些洋灰三角按照一定的规律放到摆成一排的n个格子里，其中第i个格子放入的洋灰三角数量是前一个格子的k倍再多p个，特殊地，第一个格子里放1个。
WHZ想知道把这n个格子铺满需要多少洋灰三角。

输入：

第一行有3个正整数n，k，p。

输出：
输出一行，一个正整数，表示按照要求铺满n个格子需要多少洋灰三角，由于输出数据过大，你只需要输出答案模1000000007(1e9+7)后的结果即可。

样例输入:

3 1 1

样例输出：

样例输入：

3 3 3

样例输出：

备注：

对于100%的测试数据：
1 ≤ n ≤ 1000000000
1 ≤ k,p ≤ 1000

题意：有n个格子，第一个格子装1个洋灰三角，第二个格子装前一个格子的k倍加上p，给你一个n，求出前n个格子的洋灰三角数。

思路：

Fn=Fn-1+k*An-1+p，构造出一个T矩阵

1	k	p
0	k	p
0	0	1

运用矩阵快速幂求解。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
#define ONF 0xc0c0c0c0
using namespace std;
typedef long long ll;
const ll Mod=1e9+7;
ll temp[10][10];
void multi(ll x[][10],ll y[][10])
{
    memset(temp,0,sizeof(temp));
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                temp[i][j]=(temp[i][j]%Mod+x[i][k]*y[k][j]%Mod)%Mod;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        x[i][j]=temp[i][j]%Mod;
}
void pow(ll n,ll x[][10],ll y[][10])
{
    n=n-1;
    while(n>0)
    {
        if(n%2!=0)
        {
            multi(x,y);
        }
        multi(y,y);
        n/=2;
    }
}
int main()
{
    ll n,k,p,a[10][10],res[10][10];;
    while(scanf("%lld %lld %lld",&n,&k,&p)!=EOF)
    {
        memset(res,0,sizeof(res));
        memset(a,0,sizeof(a));
        a[0][0]=1;a[0][1]=k;a[0][2]=p;
        a[1][1]=k;a[1][2]=p;a[2][2]=1;
        /*for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }*/
        for(int i=0;i<3;i++) res[i][i]=1;
        pow(n,res,a);
        ll sum=(res[0][0]%Mod+res[0][1]%Mod+res[0][2]%Mod)%Mod;
        printf("%lld
",sum);
    }
}