2

私はこの問題を解決しています：

G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n)

モジュロ1000000007。

Input

First line contains number of test cases t (t<40000). Each of the next t

行には整数n（0 <= n <2 ^ 51）が含まれます。

Output

For each test case print G(n) modulo 1000000007.

Example

Input:
2
2
4



Output:


15
714

これは私が書いたコードです：

typedef long long type;
#define check 1000000007
type x;
type y;

type f(type n)
{
    return(ceil((pow(1.618,n) - pow(-0.618,n))/((sqrt(5)*1.0))));
}
type val(type n)
{
    if(n==0)
    return 0;
    else 
    return (val(n-1)+f(4*n-1));
}
int main()
{
    cin>>x;
    while(x--)
    {
       cin>>y;
       cout<<val(y)%check<<endl;
       }
    //getch();
    return 0;
}

改善点を提案できますか？

4

4 に答える 4

1


このような問題は、ブルートフォースソリューションではなく、数学的なトリックで対処できる場合があります。

n私の意見では、とモジュロの大きな値は
、賢い解決策が存在することを示しています。もちろん、解決策を見つけるのは難しい部分です。

（これがあなたの場合に理想的かどうかはわかりませんが、別の方法を示しているだけです）

たとえば、Art of Computer Programming、Volume 1：Fundamental Algorithms Knuthは 、Fnフィボナッチ数の
閉じた形を構築するための巧妙な方法である「母関数」を使用しています。

詳細については、母関数（pdf）を参照してください。

シーケンスの母関数を気にする必要があるのはなぜですか？いくつかの答えがありますが、ここに1つあります。シーケンスの母関数を見つけることができれば、n番目の係数の閉じた形を見つけることができます。これは非常に便利です。たとえば、 x /（1-x-x 2 ）のべき級数のx nの係数の閉形式は、n番目のフィボナッチ数の明示的な式になります。[...]

于 2011-02-02T14:23:38.850 に答える
1

G（n）= G（n-1）+ f（4n-1）= G（n-2）+ f（4n-1）+ f（4n-5）など

したがって

G（n）= f（4n-1）+ f（4n-5）+ f（4n-9）... f（3）

f（n）= f（n-1）+ f（n-2）= 2f（n-2）+ f（n-3）= 3f（n-3）+ 2f（n-4）= 5f（n -4）+ 3f（n-5）f（n-5）= 3f（n-8）+ 2f（n-9）したがって、f（n）= 5f（n-4）+ 9f（n-8）+ 6f（n-9）= 5f（n-4）+ 9f（n-8）+ 18f（n-12）+ 12f（n-13）

= 5f（n-4）+ 9f（n-8）+ 18f（n-12）+ 36f（n-16）+ 24f（n-17）

いずれにせよ、係数が毎回2倍になることは明らかです。もちろん、上記から、f（n-8）などの観点からf（n-4）を定義できます。これがどこにつながるかはわかりません。

ここには系列があり、f（3）= 2およびf（2）= 1なので、最後に定数を追加します。

実際には、目的のために、この時点で2つ以上を格納することなく、1回のパスでf（n）を計算できます。上記のGの式を知っているので、f（n）の計算をパスすると、更新できます。 nが各点で3mod4と合同である場合、必要に応じてフィボナシ数を合計します。

これほど膨大な数（2の51乗）のテーブルをディスクに保存するスペースはありませんが、実際にはテーブルに格納する必要のある合計です（f（3）、f（3） ）+ f（7）、f（3）+ f（7）+ f（11）など）何かを保存する場合。

于 2011-02-02T14:56:39.083 に答える
0

では、f（）はフィボナッチ関数ですか？通常の再帰アルゴリズムを使用することをお勧めします。ただし、iの値を小さくするためのf（i）の呼び出しは非常に頻繁に繰り返されるため、キャッシュを追加することでパフォーマンスを大幅に向上させることができます。

これは、整数の静的ローカル配列を使用して行うことができます。要素が0の場合はミスなので、値を計算して配列に格納します。

そうすれば、浮動小数点演算の使用を避け、スタックがいっぱいになることはありません。

于 2011-02-02T13:19:44.227 に答える
0

の値を取得するためのより良い方法は、次のG(n)ように計算することだと思います。

type val(type n, std::vector<type> &fib)
{
  type ret = 0, s = min(type(fib.size()), n);
  for(type i=0; i < s; ++i)
      ret += fib[i];

  if(n > fib.size()){    
    fib.reserve(n);
    int tmp;
    for(type i = fib.size(); i < n; ++i){
      tmp = f(4*i+3);
      fib.push_back(tmp);
      ret += tmp;
    }

  }
  return ret;
}

（コード全体については、http：//www.ideone.com/jorMyを確認してください）

可能な限り再帰を避けてください。そうすれば、フィボナッチ関数が毎回計算されるわけではありません。

編集：私はそれを見つけるために多くの時間を費やしました（私の数学は少し錆びています）が、次のようにvalを書くこともできます：

numtype val(numtype n) {
  return ceil(2.218*pow(6.8541,n-1) - 0.018*pow(0.145898,n-1) - 0.2);
}

（ http://www.ideone.com/H1SYzのコード）

これはあなたの合計の閉じた形です。自分で見つけたい場合は（結局のところ宿題です）、ニックDの答えに従ってください。

于 2011-02-02T13:47:54.917 に答える