题目描述
婷婷是个喜欢矩阵的小朋友，有一天她想用电脑生成一个巨大的 \(n\) 行 \(m\) 列的矩阵（你不用担心她如何存储）。她生成的这个矩阵满足一个神奇的性质：若用 \(F[i,j]\) 来表示矩阵中第 \(i\) 行第 \(j\) 列的元素，则 \(F[i,j]\) 满足下面的递推式:
\[\begin{aligned} F[1, 1] &= 1 \\ F[i, j] &=a\times F[i, j-1]+b, &j\neq 1 \\ F[i, 1] &=c\times F[i-1, m]+d, &i\neq 1 \\ \end{aligned}\]递推式中 \(a,b,c,d\) 都是给定的常数。
现在婷婷想知道 \(F[n,m]\) 的值是多少，请你帮助她。由于最终结果可能很大，你只需要输出 \(F[n,m]\) 除以 \(10^9+7\) 的余数。
输入格式
包含一行有六个整数 \(n,m,a,b,c,d\)。意义如题所述。
输出格式
包含一个整数，表示 \(F[n,m]\) 除以 \(10^9+7\) 的余数。
样例 #1
样例输入 #1
3 4 1 3 2 6
样例输出 #1
85
提示
【样例1说明】
样例中的矩阵为：
\[\begin{pmatrix} 1 & 4 & 7 & 10 \\ 26 & 29 & 32 & 35 \\ 76 & 79 & 82 & 85 \\ \end{pmatrix}\]F[1, m] 从 F[1, 1]转换:
\[\begin{aligned} F[1, m] &=t1*F[1, 1] + t2\\ \end{aligned}\]\[\begin{aligned} &t1=a^{m-1},t2= S_n * b\\ &F[1, 1]=1\\ &S_n = a^0 + a^1 ... +a^{m-2} \end{aligned}\]F[2, 1] 从 F[1, m]转换:
\[\begin{aligned} F[2, 1] &=c*(t1+ t2) + d\\ \end{aligned}\]可以得到F[1, m]->F[2, m]的转移公式
\[\begin{aligned} F[2, m] &=t1*(c*F[1, m]+d)+t2 \\ \end{aligned}\]即
\[\begin{aligned} F[2, m] &=t3*F[1, m]+t4 \\ \end{aligned}\]\[\begin{aligned} t3 = c*t1\\ t4 = t1*d+t2 \end{aligned}\]同理可推出F[1, m]->F[n, m]的转移公式
\[\begin{aligned} F[n, m] &=t5*F[1, m]+t6 \\ \end{aligned}\]\[\begin{aligned} t5 = t3^{n-1}\\ t6 = t4*S_n\\ S_n = t4^0 + t4^1 ... +t4^{n-2} \end{aligned}\]同时使用费马小定理
\[\begin{aligned} a^{p-1} \equiv 1\ (mod\ p) \end{aligned}\]将m和n降次到1e9以内，可用等比数列公式+快速幂进行运算
\[S_n= \begin{cases} -x,\quad q= 1\\ (1-q^n)/(1-q), \ &q\neq 1 \end{cases} \]AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<PII, int> PPI;
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define FOR(i,s,e)for(int i=(s);i<=(e);i++)
#define mem(a, b) memset((a), (b), sizeof(a))
#define inf 0x3f3f3f3f
#define seed 13331
#define MOD1 1000000007
#define MOD2 1000000009
#define MOD3 998244353
const int N = 2e5+7;
ll qmi(ll m, ll k, ll p)
{
ll res = 1%p, t = m;
while(k)
{
if(k&1)
res = res*t % p;
t= t*t%p;
k >>=1;
}
return res;
}
ll gp(ll q, ll n)
{
return (qmi(q,n,MOD1)-1) * qmi(q-1, MOD1-2,MOD1) % MOD1;
}
void solve(int i_)
{
string s1,s2;
cin>>s1>>s2;
ll n1=0,n2=0,m1=0,m2=0;
for(auto c:s1)
{
n1 = (n1*10+c-'0')%(MOD1-1);
n2 = (n2*10+c-'0')%(MOD1);
}
for(auto c:s2)
{
m1 = (m1*10+c-'0')%(MOD1-1);
m2 = (m2*10+c-'0')%(MOD1);
}
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll t1 = qmi(a,m1-1,MOD1), t2;
if(a==1)
t2 = b*(m2-1)%MOD1;
else
t2 = b*gp(a,m1-1)%MOD1;
ll t3 = c * t1 %MOD1, t4 = (t1*d+t2)%MOD1;
ll t5 = qmi(t3, n1-1,MOD1), t6;
if(t3==1)
t6 = t4*(n2-1)%MOD1;
else
t6 = t4*gp(t3,n1-1);
ll f1m = t1+t2;
ll fnm = (t5*f1m+t6)%MOD1;
cout<<fnm;
}
int main()
{
io;
int T=1,i_;
// cin>>T;
// for(i_=1;i_<=T;i_++)
solve(i_);
return 0;
}