问题描述
九条可怜是一个肥胖的女孩.
她最近长胖了,她想要通过健身达到减肥的目的,于是她决定每天做n次仰卧起坐以达到健身的目的.
她可以将这n次动作分为若干组完成,每一次完成ai次仰卧起坐,每做完一次都会获得 \(F_{a_i}\) 点数,序列 \(F\) 满足如下关系:
\[\begin{cases} F_n=n &n<2\\ xF_n=aF_{n-1}+bF_{n-2} & n\ge2 \end{cases}
\]
\]
九条可怜每天只会做n个动作,每一个分组方案可以获得的贡献是\(\prod_{i}F_{a_i}\),她想要知道所有分组方案的贡献和.答案对\(10^9+7\)取膜.
输入格式
输入仅一行，包含四个整数 $n, x, a, b $，含义见题面。
输出格式
输出包含一个整数，表示所有健身方案的贡献和.
样例输入
3 1 1 1
样例输出
5
解析
看到这种形式的题目一般都会和矩阵快速幂优化递推有关系。不妨先考虑如何DP转移，再从优化转移入手：
设 \(f_i\) 表示当 \(n=i\) 时的答案，那么不难写出如下状态转移方程：
\[f_i=\sum_{j=0}^{i-1}f_j F_{i-j}
\]
\]
考虑想办法把式子中的求和号去掉。我们有这样的操作：
\[\begin{align}
xf_{i+1}-af_i &= x\sum_{j=0}^{i}f_jF_{i+1-j}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_iF_1+x\sum_{j=0}^{i-1}f_jF_{i+1-j}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+x\sum_{j=0}^{i-1}f_j\frac{aF_{i-j}+bF_{i-j-1}}{x}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+a\sum_{j=0}^{i-1}f_jF_{i-j}+b\sum_{j=0}^{i-1}f_jF_{i-j-1}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+b\sum_{j=0}^{i-2}f_jF_{i-j-1}+bf_{i-1}F_0\\
&=xf_i+bf_{i-1}
\end{align}
\]
xf_{i+1}-af_i &= x\sum_{j=0}^{i}f_jF_{i+1-j}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_iF_1+x\sum_{j=0}^{i-1}f_jF_{i+1-j}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+x\sum_{j=0}^{i-1}f_j\frac{aF_{i-j}+bF_{i-j-1}}{x}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+a\sum_{j=0}^{i-1}f_jF_{i-j}+b\sum_{j=0}^{i-1}f_jF_{i-j-1}-a\sum_{j=0}^{i-1}f_jF_{i-j}\\
&=xf_i+b\sum_{j=0}^{i-2}f_jF_{i-j-1}+bf_{i-1}F_0\\
&=xf_i+bf_{i-1}
\end{align}
\]
所以有\(f_i=\frac{x+a}{x}f_{i-1}+\frac{b}{x}f_{i-2}\)。
然后，就可以构造矩阵转移了。注意系数中的分母要用逆元。
代码
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod=1000000007;
struct Matrix{
int a[3][3],n,m;
}S;
int n,x,a,b;
Matrix mult(Matrix a,Matrix b)
{
Matrix c;
c.n=a.n,c.m=b.m;
for(int i=1;i<=c.n;i++){
for(int j=1;j<=c.m;j++) c.a[i][j]=0;
}
for(int i=1;i<=a.n;i++){
for(int j=1;j<=b.m;j++){
for(int k=1;k<=a.m;k++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
}
}
return c;
}
Matrix poww(Matrix a,int b)
{
b--;
Matrix ans=a,base=a;
while(b){
if(b&1) ans=mult(ans,base);
base=mult(base,base);
b>>=1;
}
return ans;
}
int pow(int a,int b)
{
int ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
signed main()
{
cin>>n>>x>>a>>b;
Matrix ans;
ans.n=1,ans.m=2;
ans.a[1][1]=1;ans.a[1][2]=0;
S.a[1][1]=(a+x)*pow(x,mod-2)%mod,S.a[2][1]=b*pow(x,mod-2)%mod,S.a[1][2]=1;
S.n=2,S.m=2;
ans=mult(ans,poww(S,n-1));
printf("%lld\n",ans.a[1][1]);
return 0;
}