ACM模版

描述

题解

很容易就能证明，我们其实只需要求出第 n 项的位数，因为很明显经过这么多次或操作后全部为 1 。

此时，我们应该想起来那个斐波那契数列的通项公式，

fib(n)=15‾‾√[(1+5‾‾√2)n−(1−5‾‾√2)n]

此时，我们用极限来看，当 n 大一些的时候，
limx→∞(1−5‾‾√2)n=0

于是当 n 较大的时候，斐波那契数列的值约为，
fib′(n)=15‾‾√(1+5‾‾√2)n

位数就是：
len=log2(fib′(n))+1

化解也就是：
len=n∗log2(1+5‾‾√2)−log2(5‾‾√)+1

通过换底公式也就变成了：
len=n∗log(1+5√2)log2−log(5‾‾√)log2+1

这里需要注意，当 n 不够大时，我们还是需要用预处理来获取准确值，longlong 的范围大概能到 92 项，所以打表出来就好了！最后再使用一下快速模幂，结果再减一就得到了正确结果哦~~~这里也不用担心模幂后结果为 0 时减一结果为负，因为貌似不存在这种为 0 的情况……

十分有趣的问题，不错哦~~~

代码

#include <iostream>
#include <cmath>

using  namespace  std;

typedef long long ll;

const int MAGIC = 93;   // 93项刚好不会爆 ll
const int MOD = 1e9 + 7;

ll n;
ll fib[MAGIC], ans;

void init()
{
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < MAGIC; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

ll pow_mod(ll x, ll n)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int  main()
{
    init();

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        if (n == 0)
        {
            cout << 0 << endl;
        }
        else if (n < MAGIC)
        {
            ll len = log(fib[n]) / log(2);
            ans = pow_mod(2, len + 1);
            cout << ans - 1 << endl;
        }
        else
        {
            ll len = n * log((1 + sqrt(5)) / 2) / log(2) - log(sqrt(5)) / log(2);
            ans = pow_mod(2, len + 1);
            cout << ans - 1 << endl;
        }  
    }

    return 0;  
}