递推式部分可以去看出题人的题解,这里提供另一种 $3\times 3$ 的矩阵构造方法。
首先根据递推式得到目标矩阵:
$$\begin{vmatrix}f_i\s_i\(2b)i\end{vmatrix}$$
然后我们观察到 $s_i=s{i-1}+f_i+(2b)i$ 中,$s_i$ 的转移需要 $f_i$,不能直接转移。但是 $f_i$ 可以通过 $f{i-1}$ 转移到,所以 $s_i$ 也可以通过 $f_{i-1}$ 转移到,只要在 $s_i$ 的转移中加上 $f_i$ 转移对应的系数就可以了。
于是可以得到如下转移矩阵:
$$\begin{vmatrix}a+b&0&a\a+b&1&a+2b\0&0&2b\end{vmatrix}$$
初始矩阵只有 $2b$ 那一项是 $1$($(2b)0$ 次方为 $1$),其他是 $0$。
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+5,p=1e9+7;
struct matrix
{
int a[4][4];
matrix(){memset(a,0,sizeof a);}
matrix operator *(matrix b)
{
matrix c;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%p)%p;
return c;
}
}base,ans;
int qp(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=ans*x%p;
x=x*x%p;
y>>=1;
}
return ans;
}
int n,A,B,m,sum;
signed main()
{
cin>>n>>A>>B>>m;
A=A*qp(100,p-2)%p;
B=B*qp(100,p-2)%p;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
sum=(sum+qp((A+B)%p,x-1)*B%p*y%p)%p;
}
base.a[1][1]=(A+B)%p;
base.a[1][3]=A;
base.a[2][1]=A+B;
base.a[2][2]=1;
base.a[2][3]=(A+2*B%p)%p;
base.a[3][3]=2*B%p;
ans.a[3][1]=1;
while(n)
{
if(n&1) ans=base*ans;
base=base*base;
n>>=1;
}
cout<<(sum+ans.a[2][1])%p;
return 0;
}