问题描述
九条可怜是一个肥胖的女孩.
她最近长胖了,她想要通过健身达到减肥的目的,于是她决定每天做n次仰卧起坐以达到健身的目的.
她可以将这n次动作分为若干组完成,每一次完成ai次仰卧起坐,每做完一次都会获得 (F_{a_i}) 点数,序列 (F) 满足如下关系:
[egin{cases} F_n=n &n<2\ xF_n=aF_{n-1}+bF_{n-2} & nge2 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}
]
考虑想办法把式子中的求和号去掉。我们有这样的操作：
[egin{align}
xf_{i+1}-af_i &= xsum_{j=0}^{i}f_jF_{i+1-j}-asum_{j=0}^{i-1}f_jF_{i-j}\
&=xf_iF_1+xsum_{j=0}^{i-1}f_jF_{i+1-j}-asum_{j=0}^{i-1}f_jF_{i-j}\
&=xf_i+xsum_{j=0}^{i-1}f_jfrac{aF_{i-j}+bF_{i-j-1}}{x}-asum_{j=0}^{i-1}f_jF_{i-j}\
&=xf_i+asum_{j=0}^{i-1}f_jF_{i-j}+bsum_{j=0}^{i-1}f_jF_{i-j-1}-asum_{j=0}^{i-1}f_jF_{i-j}\
&=xf_i+bsum_{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
",ans.a[1][1]);
return 0;
}