【训练题36：数学】斐波那契各项幂次前缀和
正题
- 【链接】
斐波那契各项幂次前缀和 - 【题意】给定
n
,
K
n,K
n,K，求出：
∑
i
=
1
n
(
F
i
b
i
)
K
(
m
o
d
1
e
9
+
9
)
\sum_{i=1}^n (Fib_i)^{K}\pmod {1e9+9}
i=1∑n(Fibi)K(mod1e9+9)
其中F
i
b
i
Fib_i
Fibi 表示第i
i
i 个斐波那契数字，F
i
b
[
]
=
[
1
,
1
,
2
,
3
,
5
,
8
,
⋯
]
Fib[]=[1,1,2,3,5,8,\cdots]
Fib[]=[1,1,2,3,5,8,⋯] - 【范围】
1
≤
n
≤
1
0
18
1\le n\le 10^{18}
1≤n≤1018
1
≤
K
≤
1
0
5
1\le K\le 10^5
1≤K≤105
解法
- 由于
K
K
K 比较大，我们不能直接用矩阵快速幂去做。考虑斐波那契数字的显式公式：
具体内容见我的博客：【小组专题三：斐波那契专题】
f
n
=
1
5
(
α
n
−
β
n
)
f_n=\frac{1}{\sqrt 5}(\alpha^n-\beta^n)
fn=51(αn−βn)
其中α
=
5
+
1
2
,
β
=
5
−
1
2
\alpha=\frac{\sqrt5+1}{2},\beta=\frac{\sqrt5-1}{2}
α=25+1,β=25−1
于是，我们要求的内容就变成了：(以下式子皆省略模数)
∑
i
=
1
n
(
F
i
b
i
)
K
=
∑
i
=
1
n
1
5
K
(
α
i
−
β
i
)
K
=
1
5
K
∑
i
=
1
n
(
α
i
−
β
i
)
K
\sum_{i=1}^n (Fib_i)^{K}=\sum_{i=1}^n \frac{1}{\sqrt5^K}(\alpha^i-\beta^i)^K= \frac{1}{\sqrt5^K}\sum_{i=1}^n(\alpha^i-\beta^i)^K
i=1∑n(Fibi)K=i=1∑n5K1(αi−βi)K=5K1i=1∑n(αi−βi)K
设1
5
K
=
R
e
\frac{1}{\sqrt5^K}=Re
5K1=Re
我们只要求后面的一个二项式即可。我们把二项式拆开来，得到：
F
i
b
n
=
R
e
(
(
−
1
)
0
C
K
0
α
K
n
β
0
n
+
(
−
1
)
1
C
K
1
α
(
K
−
1
)
n
β
1
⋅
n
+
⋯
)
Fib_n=Re\Big( (-1)^0C_K^0 \alpha^{Kn}\beta^{0n} + (-1)^1C_K^1 \alpha^{(K-1)n}\beta^{1\cdot n} +\cdots\Big)
Fibn=Re((−1)0CK0αKnβ0n+(−1)1CK1α(K−1)nβ1⋅n+⋯)
考虑到第i
i
i 项，即系数为(
−
1
)
i
C
K
i
α
(
K
−
i
)
n
β
i
⋅
n
(-1)^iC_K^i\alpha^{(K-i)n}\beta^{i\cdot n}
(−1)iCKiα(K−i)nβi⋅n。
考虑到每一个n
n
n，该项成等比数列，即：公比为α
(
K
−
i
)
β
i
\alpha^{(K-i)}\beta^i
α(K−i)βi，用等比公式求出即可。
问题一 ：根号五？
- 【Q】考虑到需要多次计算出
5
\sqrt5
5 的值，在取模意义下怎么得到？ - 【A】就是二次剩余的知识，见我的博客 【算法讲18：二次剩余】
用c
i
p
o
l
l
a
cipolla
cipolla 即可预处理算出该模意义下的5
\sqrt5
5 的值。
问题二 ：公比模意义为一？
- 【Q】根据等比求和，公比必须不为
1
1
1。但是α
(
K
−
i
)
β
i
\alpha^{(K-i)}\beta^i
α(K−i)βi 在取模意义下可能为1
1
1 咋办？ - 【A】如果公比为
1
1
1，那么每一项取模意义下值都是第一项。贡献为R
e
×
(
−
1
)
i
×
n
Re\times (-1)^i\times n
Re×(−1)i×n
核心代码
- 时间复杂度：
O
(
K
log
K
)
O(K\log K)
O(KlogK)
/*
_ __ __ _ _
| | \ \ / / | | (_)
| |__ _ _ \ V /__ _ _ __ | | ___ _
| '_ \| | | | \ // _` | '_ \| | / _ \ |
| |_) | |_| | | | (_| | | | | |___| __/ |
|_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|
__/ |
|___/
*/
const ll sq5 = 383008016;
const ll iv2 = inv(2);
ll fac[MAX],ivfac[MAX];
ll C(int n,int m){
if(m < 0 || m > n)return 0;
return fac[n] * ivfac[m] % MOD * ivfac[n - m] % MOD;
}
void init(int n){
fac[0] = 1;
for(int i = 1;i <= n;++i){
fac[i] = fac[i-1] * i % MOD;
}
ivfac[n] = inv(fac[n]);
for(int i = n - 1;i >= 0;--i){
ivfac[i] = ivfac[i+1] * (i + 1) % MOD;
}
}
int main()
{
init((int)1e5);
int T;scanf("%d",&T);
while(T--){
ll n,k;
scanf("%lld%lld",&n,&k);
ll xi = inv(qpow(sq5,k));
ll alpha = (1LL + sq5) * iv2 % MOD;
ll beta = (1LL - sq5 + MOD) * iv2 % MOD;
ll res = 0;
for(int i = 0;i <= k;++i){
ll tmp = C(k,i);
if(i & 1)tmp = (-tmp + MOD) % MOD;
ll shu = qpow(alpha,k-i) * qpow(beta,i) % MOD;
ll shu2= qpow(shu,n);
if(shu == 1){ /// 公比为 1
res = (res + n % MOD * tmp % MOD) % MOD;
continue;
} /// 等比数列求和公式
tmp = tmp * shu % MOD * (shu2 - 1) % MOD * inv(shu - 1) % MOD;
res = (res + tmp) % MOD;
}
res = res * xi % MOD;
res = (res + MOD) % MOD;
printf("%lld\n",res);
}
return 0;
}