传送门 题目描述：
Input
共1行，4个整数数p, q, r, n中间用空格分隔(1 <= p, q, r, n<=1000000000)。
Output
对于每一个数据，在一行中输出答案。
Input示例
2 2 1 1
Output示例
3
解题思路：
令 f(n)=∑ni=0ai∗bn−i ，将其展开有： f(n)=a0∗bn+a1∗bn−1+...+an∗b0 同理 f(n+1) 也可写出： f(n+1)=∑n+1i=0ai∗bn+1−i f(n+1)=a0∗bn+1+a1∗bn+...+an+1∗b0 通过观察，发现如下公式成立： f(n+1)=f(n)∗q+an+1∗b0 根据这个递推式，我们可以构造一个矩阵 A ： A=⎛⎝⎜qb0∗pb00p1001⎞⎠⎟ (f(n),an,r)∗A=(f(n+1),an+1,r) ，即有：
(f(0),a0,r)∗An=(f(n+1),an+1,r)
通过矩阵快速幂就可以推出 f(n)%1e9+7 代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; typedef long long LL; const LL MOD = 1e9+7; const int MAXN = 3; struct Matrix{ LL mat[MAXN][MAXN]; }; Matrix Multi(Matrix a, Matrix b){ Matrix c; for(int i=0; i<MAXN; i++){ for(int j=0; j<MAXN; j++){ c.mat[i][j] = 0; for(int k=0; k<MAXN; k++){ c.mat[i][j] = c.mat[i][j] + a.mat[i][k]*b.mat[k][j] % MOD; c.mat[i][j] = (c.mat[i][j] % MOD + MOD) % MOD; } } } return c; } Matrix Pow(Matrix a, LL n){ Matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); for(int i=0; i<MAXN; i++) ans.mat[i][i] = 1; while(n){ if(n & 1) ans = Multi(ans, a); n>>=1; a = Multi(a, a); } return ans; } int main() { LL p, q, r, n; while(~scanf("%lld%lld%lld%lld",&p,&q,&r,&n)){ Matrix ans; ans.mat[0][0] = q, ans.mat[0][1] = 0, ans.mat[0][2] = 0; ans.mat[1][0] = 3*p%MOD, ans.mat[1][1] = p, ans.mat[1][2] = 0; ans.mat[2][0] = 3, ans.mat[2][1] = 1, ans.mat[2][2] = 1; ans = Pow(ans, n); LL ret = (ans.mat[2][0]*r%MOD+MOD)%MOD; cout<<ret<<endl; } return 0; }