斐波那契数列线性dp-白红宇的个人博客

斐波那契数列线性dp

发布日期：2021-09-25 23:57:39 浏览次数：10 分类：技术文章

本文共 2170 字，大约阅读时间需要 7 分钟。

斐波那契数列

时间限制: 1 Sec 内存限制: 128 MB

题目描述

斐波那契数列F满足如下性质：F1=1,F2=2,Fi+2=Fi+1+Fi。

对于一个正整数n，它可以表示成一些不同的斐波那契数列中的数的和。你需要求出：有多少种不同的方式可以表示出n？

输入

输入有多组数据。第一行为一个整数T，表示数据组数。

接下来T行，每行一个正整数n。

输出

输出T行，为T组数据的答案。

样例输入 Copy

样例输出 Copy

提示

样例解释：16=3+13=3+5+8=1+2+13=1+2+5+8

对于100%的数据，满足1≤T≤10，1≤n≤1018。

首先呢，依据二进制可以表示所有数的思想，猜测斐波那契数列也可表示所有数，显然猜想是正确的，多写即可就可以找出来规律了。

根据数学知识：斐波那契的第 i 个数可以拆成的表示形式有 ( i - 1 ) / 2 个(打表也可以找出来规律)。

(1)当当前的n正好是斐波那契数列中的数的时候，直接就可以输出 ( n - 1 ) / 2 + 1 即为答案。

(2)当当前数不是斐波那契数列中的数的时候，那么一定可以找到若干的斐波那契数列中的数来构成 n ，将这些数拿出来，找他们分解得到的所有不同的方案。

难点是第二步怎么找到所有不同的方案，自己写写情况，发现比较难，需要考虑两个状态：分解或者不分解。那么就可以开一个数组 f [ i ] [ j ] i 表示当前位数 j 表示当前的数分解还是不分解。

先给出转移方程吧： 1 表示分解 0 表示不分解

f [ i ] [ 0 ] = f [ i - 1 ] [ 0 ] + f [ i - 1 ] [ 1 ]

f [ i ] [ 1 ] = f [ i - 1 ] [ 1 ] * ( a [ i ] - a [ i - 1 ] >> 1 ) + f [ i - 1 ] [ 0 ] * ( a [ i ] - a [ i - 1 ] - 1 >> 1 )

解释下：如果不分解当前元素，那么方案数等于前两个之和，并且当前 i 不能被 i + 1 所使用。 如果分解当前元素，那么方案数等于 (1)当前元素与上一个元素中间的数 + 上一个元素和 与分解上一个元素的方案相乘 ( 因为只有上一个元素分解了，i - 1 这个位置才能空出来 ) (2) 当前元素与上一个元素之间的数 与 不分解上一个元素的方案相乘 ( 因为上一个元素没有分解，那么 i - 1 这个位置被上一个元素占领了 )

代码有点小乱，可以把前面特判 n 都给去掉。~~一开始被自己sb想法给蛊惑了~~

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;LL n,cnt;LL fib[N],ans;LL f[N][2];bool st[N];void init(){ fib[1]=1,fib[2]=2; for(int i=3;;i++) { fib[i]=fib[i-1]+fib[i-2]; if(fib[i]>=1e18) { cnt=i-1; break; } }}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); init(); int t; scanf("%d",&t); while(t--) { scanf("%lld",&n); if(n==1) { puts("1"); continue; } if(n==2) { puts("2"); continue; } int pos=lower_bound(fib+1,fib+1+cnt,n)-fib; if(fib[pos]==n) ans=(pos-1)/2+1; else { vector
                
                 v; pos--; for(int i=pos;i>=1;i--) { if(fib[i]<=n) v.push_back(i),n-=fib[i]; if(!n) break; } int l=v.size(); f[l-1][0]=1,f[l-1][1]=(v[l-1]-1)/2; for(int i=l-2;i>=0;i--) { f[i][0]=f[i+1][0]+f[i+1][1]; f[i][1]=((v[i]-v[i+1]-1)/2)*f[i+1][0]+((v[i]-v[i+1])/2)*f[i+1][1]; } ans=f[0][1]+f[0][0]; } printf("%lld\n",ans); } return 0;}

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105896205 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：好朋友容斥原理

下一篇：upc bus 线性dp

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章