Description
第二关和很出名的斐波那契数列有关,地球上的OIer都知道:F1=1, F2=2, Fi = Fi-1 + Fi-2,每一项都可以称为斐波那契数。现在给一个正整数N,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数,那么对一个N最多可以写出多少种方案呢?
Input
只有一个整数N。
Output
一个方案数
Sample Input
16
Sample Output
4
HINT
Hint:16=3+13=3+5+8=1+2+13=1+2+5+8
对于30%的数据,n<=256
对于100%的数据,n<=10^18
————————————————————————————–
题解
首先,任何数都能分解成几个斐波那契数列的和(一定有解),所以先将这个数字拆成几个斐波那契数相加的形式,编号记为pos[i],又因为每个斐波那契数可以分解继续成接下来的两项之和,我们就要考虑pos[i]与pos[i-1]的位置关系与其元素是否继续分解。dp[i][0/1]表示斐波那契中第i项替换或不替换。转移方程为: dp[i][1]=dp[i-1][0]+dp[i-1][1]; dp[i][0]=dp[i-1][0]*(pos[i]-pos[i-1]>>1)+dp[i][1]*(pos-pos[i-1]-1>>1);
代码
#includeusing namespace std;long long n,fab[90];int cnt,pos[90],dp[90][2];int main(){ fab[1]=1;fab[2]=2; cin>>n; for(register int i=3;i<=85;i++) fab[i]=fab[i-1]+fab[i-2]; for(register int i=85;i>=1;i--) if(n>=fab[i]){ n-=fab[i]; pos[++cnt]=i; } sort(pos+1,pos+1+cnt); dp[1][1]=1;dp[1][0]=pos[1]-1>>1; for(register int i=2;i<=cnt;i++){ dp[i][1]=dp[i-1][0]+dp[i-1][1]; dp[i][0]=dp[i-1][0]*(pos[i]-pos[i-1]>>1)+dp[i-1][1]*(pos[i]-pos[i-1]-1>>1); } cout< <