相关疑难解决方法(0)

该问题需要生成n-th与Fibonacci序列类似的序列元素.但是,它有点棘手,因为n它非常大(1 <= n <= 10 ^ 9).然后答案模1000000007.序列定义如下:

使用生成函数,我得到以下公式:

如果我使用序列方法,那么答案可以是模数,但它运行得非常慢.事实上,我有time limit exceed很多次.我还尝试使用表来预生成一些初始值(缓存),但仍然不够快.另外,array/vector与(10 + 9)相比,我可以在(C++)中存储的最大元素数量太少,所以我猜这种方法也不起作用.
如果我使用直接配方,那么它运行速度非常快,但仅限n于此.对于n大,double将被截断,加上我将无法使用该数字修改我的答案,因为modulo仅适用于整数.
我没有想法,我认为必须有一个非常好的技巧来解决这个问题,不幸的是我只是想不到一个.任何想法将不胜感激.

这是我最初的方法:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
#include <sstream>
#include <cstdio>
#include <map>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

ull count_fair_coins_by_generating_function(ull n) {
    n--;
    return 
        (sqrt(3.0) + 1)/((sqrt(3.0) - 1) * 2 * …