HDU 6755 - Fibonacci Sum(二项式定理+推式子)
2021/5/2 18:28:50
本文主要是介绍HDU 6755 - Fibonacci Sum(二项式定理+推式子),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题面传送门
其实是一道还好的题罢,虽然做了我 2147483647(bushi,其实是 1.5h),估计也只是因为 HDU 不支持数据下载所以错误总 debug 出来
首先看到 \(10^9+9\) 及斐波那契数列,顿时心里一个激灵,这题和通项公式逃不掉了(
套用斐波那契数列通项公式 \(f_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)\) 得:
\[\begin{aligned} \text{Ans}&=\sum\limits_{i=0}^nF_{ic}^k \\&=\sum\limits_{i=0}^n(\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic}))^k \\&=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic})^k \end{aligned} \]看到二项式的 \(k\) 次方,可以套路地想到二项式定理,用二项式定理展开一下可继续推得:
\[\begin{aligned} \text{Ans}&=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic})^k\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{1+\sqrt{5}}{2})^{icj}(-(\dfrac{1-\sqrt{5}}{2})^{ic})^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{1+\sqrt{5}}{2})^{icj}(\dfrac{1-\sqrt{5}}{2})^{ic(k-j)}(-1)^{k-j} \end{aligned} \]方便起见,我们设 \(A=\dfrac{1+\sqrt{5}}{2},B=\dfrac{1-\sqrt{5}}{2}\),那么式子可进一步化为
\[\begin{aligned} \text{Ans} &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}A^{icj}B^{ic(k-j)}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}A^{icj}B^{ick}\dfrac{1}{B^{icj}}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{A}{B})^{icj}B^{ick}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{j=0}^k(-1)^{k-j}\dbinom{k}{j}\sum\limits_{i=0}^n(\dfrac{A}{B})^{icj}B^{ick} \end{aligned} \]推到这里,前面一个 \(\sum\) 显然直接枚举是不会出问题的,至于后面一个 \(\sum\),如果我们设 \(P=(\dfrac{A}{B})^{cj}\times B^{ck}\),那么里面的式子可写为 \(\sum\limits_{i=0}^nP^i\),这显然就是一个等比数列求和的形式,直接求即可。
时间复杂度 \(Tk\log n\),顺带说一句,本题略微有点卡常,有以下卡常技巧:
- 式子里有些东西是可以预处理出来的,大可不必每枚举一遍 \(j\) 都重新快速幂计算一遍,否则常数肯定上天
- 在等比数列求和时,由于 \(10^9+9\) 是质数,可以通过欧拉降幂 \(a^m\equiv a^{m\bmod (10^9+8)}\pmod{10^9+9}\) 减少快速幂的指数,这样常数可小一半
const int S5=383008016; const int MOD=1e9+9; const int INV2=5e8+5; const int MAXN=1e5; int qpow(int x,ll e){ int ret=1; for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD; return ret; } int IV5,A,B,MUL,fac[MAXN+5],ifac[MAXN+5]; void init_fac(int n){ for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD; } int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;} int sum(int x,ll y){if(x==1) return (y+1)%MOD;return 1ll*(qpow(x,(y+1)%(MOD-1))-1+MOD)*qpow((x-1+MOD)%MOD,MOD-2)%MOD;} void solve(){ ll n,c;int k;scanf("%lld%lld%d",&n,&c,&k);c%=(MOD-1); int mul=qpow(IV5,k),ans=0,M=qpow(qpow(B,c),k),stp=qpow(MUL,c); for(int i=0,pw=1;i<=k;i++,pw=1ll*pw*stp%MOD){ int t=1ll*pw*M%MOD; int add=1ll*binom(k,i)*sum(t,n)%MOD; if((k-i)&1) ans=(ans-add+MOD)%MOD; else ans=(ans+add)%MOD; } ans=1ll*ans*mul%MOD;printf("%d\n",ans); } int main(){ IV5=qpow(S5,MOD-2); A=1ll*(1+S5)*INV2%MOD; B=1ll*(1-S5+MOD)*INV2%MOD; MUL=1ll*A*qpow(B,MOD-2)%MOD; init_fac(MAXN);int qu;scanf("%d",&qu); while(qu--) solve(); return 0; }
这篇关于HDU 6755 - Fibonacci Sum(二项式定理+推式子)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验