题解 CF392C 【Yet Another Number Sequence】
cqbzlym
·
·
题解
Description
题意简述
设 F_i 表示Fibonacci数列的第 i 项，即 F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}。
设 A_i=F_i\times i^k(k\leqslant 40)，你的任务是求出其前 n 项和 (n\leqslant 10^{18})\bmod 10^9+7 的结果。
Solution
注意到Fibonacci，n\leqslant 10^{18} 等关键词，明摆着就是一道矩阵加速嘛。
但是，，，(i-1)^k 怎么转移到 i^k 呢？
BDFS了一大堆后，发现了方法：二项式定理。
顺便还得把 $i^1,i^2,i^3,\cdots,i^k$ 丢进去，然后 $(i-1)^x$ 就可以直接转换成 $i^x$。
那么 $i^x$ 也得转换为 $(i+1)^x$，所以关键在于 $i^x$ 怎么转换为 $(i+1)^x$。
* 那这不是又回到原问题上了吗！
* 咱不要急，先慢慢看
经过作者一阵乱搞，发现矩阵乘法是处理不了 $A_i$ 的。
所以只能把矩阵里的 $i^1,i^2,\cdots,i^k$ 都乘上一个 $F_i$ 来充数。
那么我们看一看 $F_{i+1}\times(i+1)^k$ 是怎么得到的：
$$
\begin{aligned}
F_{i+1}\times(i+1)^k&=(F_{i-1}+F_i)\times(i+1)^k\\
&=F_{i-1}\times(i+1)^k+F_i\times(i+1)^k\\
&=F_{i-1}\times[(i-1)+2]^k+F_i\times[(i)+1]^k
\end{aligned}
$$
是时候亮出二项式定理了！
我们都知道，二项式定理是一个酱紫的东西：
$$
(x+y)^k=\sum\limits_{i=0}^kC_k^ix^iy^{k-i}
$$
代入到 $[(i-1)+2]^k$ 中来，就是：
$$
[(i-1)+2]^x=\sum\limits_{j=0}^xC_x^j(i-1)^j2^{x-j}
$$
而我们刚好有 $(i-1)^j$。
$C_x^j\times2^{x-j}$ 就是 $(i-1)^j$ 在加速矩阵里对应的系数。
又代入到 $[(i)+1]^x$ 中，得：
$$
[(i)+1]^x=\sum\limits_{j=0}^xC_x^ji^j
$$
挺巧的，我们也有 $i^j$。
$C_x^j$ 就是 $i^j$ 在加速矩阵中对应的系数。
设 $S_x=\sum\limits_{i=1}^xA_i$。
那么初始矩阵就长这样：
$$
[F_1,F_2,S_1,F_1\times1^1,F_1\times 1^2,\cdots,F_1\times1^k,F_2\times2^1,F_2\times2^2,\cdots,F_2\times2^k]
$$
转移一步后长这样：
$$
[F_2,F_3,S_3,F_2\times2^1,F_2\times2^2,\cdots,F_2\times2^k,F_3\times3^1,F_3\times3^2,\cdots,F_3\times3^k]
$$
转移 $n-1$ 步后的最终矩阵长这样：
$$
[F_n,F_{n+1},S_n,F_n\times n^1,F_n\times n^2,\cdots,F_n\times n^k,F_{n+1}\times(n+1)^1,F_{n+1}\times(n+1)^2,\cdots,F_{n+1}\times(n+1)^k]
$$
加速矩阵长这样：
$$
\begin{bmatrix}
&F_i&F_{i+1}&S_i&F_i\times i^1&F_i\times i^2&\cdots&F_i\times i^k&F_{i+1}\times(i+1)^1&F_{i+1}\times(i+1)^2&\cdots&F_{i+1}\times(i+1)^k
\\
F_{i-1}(\times(i-1)^0)&0&1&0&0&0&\cdots&0&2^{1-0}\times C_1^0=2&2^{2-0}\times C_2^0=4&\cdots&2^{k-0}\times C_k^0\\
F_{i}(\times i^0)&1&1&0&0&0&\cdots&0&C_1^0=1&C_2^0=1&\cdots&C_k^0\\
S_{i-1}&0&0&1&0&0&\cdots&0&0&0&\cdots&0\\
F_{i-1}\times(i-1)^1&0&0&0&0&0&\cdots&0&2^{1-1}\times C_1^1=1&2^{2-1}\times C_2^1=4&\cdots&2^{k-1}\times C_k^1\\
F_{i-1}\times(i-1)^2&0&0&0&0&0&\cdots&0&0&2^{2-2}\times C_2^2=1&\cdots&2^{k-2}\times C_k^2\\
\cdots&\vdots&\vdots&\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\
F_{i-1}\times(i-1)^k&0&0&0&0&0&\cdots&0&0&0&\cdots&2^{k-k}\times C_k^k\\
F_i\times i^1&0&0&0&1&0&\cdots&0&C_1^1=1&C_2^1=2&\cdots&C_k^1\\
F_i \times i^2&0&0&0&0&1&\cdots&0&0&C_2^2=1&\cdots&C_k^2\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\
F_i\times i^k&0&0&1&0&0&\cdots&0&0&0&\cdots&C_k^k
\end{bmatrix}
$$
（这个$\LaTeX$ 是给人打的吗。。。）
好了，除了初始化麻烦点，代码还是比较简单的。
### Code
时间复杂度 $\mathcal O($能过$)
感谢@w23c3c3 大巨佬让我逃离了手推 k=40 大数据然后真·清明节快乐的厄运。
#include<cstdio>
#include<cstring>
#define int long long
const int mod=1e9+7;
const int maxn=105;
struct Matrix{
int n,m;
int c[maxn][maxn];
Matrix(int N=0,int M=0){
n=N,m=M;
memset(c,0,sizeof(c));
}
Matrix operator*(const Matrix a)const{
int l=n,r=a.m;
Matrix x=Matrix(l,r);
for(int i=1;i<=l;++i){
for(int j=1;j<=r;++j){
for(int k=1;k<=m;++k){
x.c[i][j]+=c[i][k]*a.c[k][j];
x.c[i][j]%=mod;
}
}
}
return x;
}
}A,B;
int n,k,x=4;
int f[45][45];
Matrix pow(Matrix&x,int b){
Matrix ans=Matrix(x.n,x.m);
for(int i=1;i<=x.m;++i)
ans.c[i][i]=1;
while(b){
if(b&1)
ans=x*ans;
x=x*x;
b>>=1;
}
return ans;
}
inline void init(void){
f[0][0]=1;
for(int i=1;i<=k;++i){
f[i][0]=1;
for(int j=1;j<=i;++j)
f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
return;
}
signed main(){
scanf("%lld%lld",&n,&k);
init();
A=Matrix(1,3+(k<<1));
A.c[1][1]=1;A.c[1][2]=2;A.c[1][3]=1;
for(int i=1;i<=k;++i){
A.c[1][3+i]=1;
A.c[1][k+3+i]=x%mod;
x<<=1;
}
B=Matrix(3+(k<<1),3+(k<<1));
B.c[2][1]=1;
B.c[1][2]=B.c[2][2]=1;
B.c[3][3]=B.c[3+(k<<1)][3]=1;
for(int i=1;i<=k;++i){
B.c[1][i+k+3]=(1ll<<i)%mod;
B.c[3+k+i][3+i]=1;
B.c[2][3+i+k]=1;
}
for(int i=1;i<=k;++i){
for(int j=i;j<=k;++j){
B.c[3+i][3+k+j]=(((1ll<<j-i)%mod)*f[j][i])%mod;
B.c[3+k+i][3+k+j]=f[j][i];
}
}
A=A*pow(B,n-1);
printf("%lld",A.c[1][3]);
return 0;
}