Editorial for Fibonacci Sequence


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

ll fib[91], f[71][2], g[71][2];
int save[70];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    fib[0] = fib[1] = 1;
    FOR(i,2,90) fib[i] = fib[i-1] + fib[i-2];

    f[1][0] = f[1][1] = 1;
    FOR(i,2,70) {
        f[i][0] = f[i-1][0] + f[i-1][1];
        f[i][1] = f[i-1][0];
    }

    g[1][0] = 0; g[1][1] = 1;
    FOR(i,2,70) {
        g[i][0] = g[i-1][0] + g[i-1][1];
        g[i][1] = g[i-1][0] + f[i][1];
    }

    ll len = 0, nBit = 0, n, res = 0; cin >> n;

    while (nBit < n) {
        len++; nBit += f[len][1] * len;
        res += g[len][1];
    }
    res -= g[len][1]; nBit -= f[len][1] * len;

//    cout << res << ' ' << nBit << ' ' << len << endl;

    ll diff = 0;
    ll u = (n - nBit) / len;
    if ((nBit - n) % len) { u++; diff = (nBit + u * len) - n; }

//    cout << u << ' ' << diff << endl;

    int l = len;
    save[1] = 1; res += u;
//    cout << res << endl;
    FOR(now,2,len) {
        l--;
        if (f[l][0] >= u) {
            save[now] = 0;
        }
        else {
            save[now] = 1;
            u -= f[l][0];
            res += u + g[l][0];
        }
    }
//    FOR(x,1,len) cout << save[x]; cout << endl;
    FORD(x,len,len-diff+1) res -= save[x];
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

long long a[200],f[200],u[200];

long long xuly(long long n)
{
    //int flag = 0; 
    for(int i = 1;;i++)
    {
        if(a[i]==n)
            return f[i];
        else if(a[i]>n)
            return f[i-1]+xuly(n-a[i-1])+n-a[i-1];
    }

}

int main()
{
    long long Nmax = 1; for(int i = 1;i<=15;i++) Nmax = Nmax*10;
    a[1] = 1; a[2] = 2; f[1] = 1; f[2] = 2; u[1]=1; u[2] = 3;
    for(int i = 3;;i++)
    {
        a[i] = a[i-1]+a[i-2];
        f[i] = a[i]-a[i-1]-1+f[i-2]+f[i-1];
        u[i] = u[i-1]+(i-1)*(a[i]-a[i-1])+1;
        if(a[i]>Nmax)
             break; 
    }
    long long n,KQ = 0;
    int flag = 0;
    scanf("%lld",&n);
    for(int i = 1;;i++)
    {
        if(u[i]>n)
        {
            flag = i-1;
            break;
        }
    }
    long long N = (n-u[flag])/flag+a[flag];
    KQ = xuly(N);
    long long m =  (n-u[flag])%flag;
    long long M = N+1;
    for(int i = 1;;i++)
    {
        if(a[i]>M)
        {
            for(int j = 1;j<=m;j++)
            {
                if(M==0)
                     break;
                else if(M>=a[i-j])
                {
                     M = M-a[i-j];
                     KQ++;
                }
            }
            break;
        }
    }
    printf("%lld",KQ);
  // getch();                   
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

long long L,cnt,ret;
long long num[105],fibo[105],numOne[105];

string convert(long long x)
{
    if (x < 2) return "0";
    for (int i = 0; ; i++) if (fibo[i] > x)
    {
        string ans = "";
        for (int j = i - 1; j; j--) if (x >= fibo[j])
        {
            x -= fibo[j];  ans += '1';
        }
        else ans += '0';
        return ans;
    }
}

long long add(long long x)
{
    if (x <= 0) return 0;
    if (x == 1) return 1;
    long long sum = 0;
    for (int i = 0; ; i++)
      if (sum + num[i] <= x) sum += num[i];
      else return numOne[i - 1] + (x - sum + 1) + add(x - sum);
}

int main()
{
    //freopen("fibo.in","r",stdin);

    fibo[0] = fibo[1] = 1;
    for (int i = 2; i <= 95; i++) fibo[i] = fibo[i - 1] + fibo[i - 2];
    num[0] = num[1] = 1;

    numOne[0] = 0;  numOne[1] = 1;

    while (cin >> L)
    {
        if (L < 1)
        {
            printf("0\n");  continue;
        }
        if (L < 2)
        {
            printf("1\n");  continue;
        }

        L--;  ret = 1;
        for (int i = 2; ; i++)
        {
            num[i] = cnt = fibo[i - 1];
            numOne[i] = numOne[i - 1] + numOne[i - 2] + cnt;
            if (L/cnt >= i)
            {
                L -= 1LL * cnt * i;  ret += cnt + numOne[i - 2];
            }
            else
            {
                long long addmore = L/i;  L %= i;
                ret += addmore + add(addmore - 1);
                if (L)
                {
                    long long sum = 0;
                    for (int j = 1; j < i; j++) sum += num[j];
                    string parse = convert(sum + addmore + 1);
                    for (int j = 0; j < L; j++) if (parse[j] == '1') ret++;
                }
                break;
            }
        }
        printf("%lld\n", ret);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.