题目描述
输入
一行两个正整数n,m。n<=10^18,m<=10^6
输出
一行一个整数f(n)
样例输入
4 2
样例输出
3
题解
这里简化下题意:定义fn( x )=f( fn-1( x ) ),已知f(1)=1,且对于i>1有 f(i)=i - fm(i-1),求 f(n)。
先考虑m=1:f(i) = i-f(i-1),打个表,发现这就是当n为偶数时除以2,n为奇数时+1除以2。
然后当m=2时:f(i)=i-f(f(i-1)),先打表,如果f(i)=k,就把k向 i 连边,那么我们就得到了一棵树,如下图:
容易发现,从第二层开始,每层的个数构成了斐波拉契数列,并且这里有个很难发现的性质,对于每个结点,它的值一定可以表示成几个斐波拉契数之和,将这些斐波拉契数在斐波拉契数列里向后移动一个,然后这些数之和就是这个结点的儿子结点的值,换句话说,把一个结点 i 贪心的从大往小拆成几个斐波拉契数,再把这些数在斐波拉契数列里向前移动一个,就得到了f(i)的答案。
例如:结点16可以拆成13+3,往前移动一位就是8+2=10,所以f(16)=10。于是m=2就解决了。
我们将上面的规律推广,得到一个类斐波拉契数列:f(i) = f(i-1)+f(i-m) ,那么将n分解为几个类斐波拉契数的和,再将这些数在这个类斐波拉契数列里向前移动一位,加起来即为答案。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long longll n,m,x,t; ll f[5000000],ans,a[5000000];void fj(){for(int i=1;;i++)if(f[i]>n) {a[++t]=f[i-1-1];n-=f[i-1];break;} }int main(){cin>>n>>m;f[0]=1;for(int i=1;i<=m;i++) f[i]=1;for(int i=m+1;;i++){f[i]=f[i-1]+f[i-m];if(f[i]>n){x=i-1; break;}} a[++t]=f[x-1];n-=f[x];while(n) fj();for(int i=1;i<=t;i++) ans+=a[i];cout<<ans;return 0; }