1

私はSPOJ（http://www.spoj.pl/problems/REC/）でこの問題を解決しようとしていました

F(n) = a*F(n-1) + bF(n) Mod (m) どこを見つけなければならないか

0 <= a, b, n <=  10^100
       1 <= M <= 100000
F(0)=1

私はJAVAのBigIntegerでそれを解決しようとしていますが、0からnまでのループを実行すると、TLEが取得されます。どうすればこの問題を解決できますか？誰かがヒントを与えることができますか？ソリューションを投稿しないでください。それを効率的に解決する方法についてのヒントが欲しいです。

4

2 に答える 2

1

剰余 mod (m) のパターンは、ピジョンホールの原理により、線形回帰の繰り返しパターンを持ち、長さ <= m であることに注意してください。最初の m エントリを計算するだけでよく、n の実際の値の F(n) にどのエントリが適用されるかを計算します。

また、より単純な問題を解決するのにも役立ちます。a=2、b=1、m=5、n=1000 など、非常に小さな値を選びましょう。

  • F(0) = 1
  • F(1) = 2*F(0) + 1 = 2*1 + 1 = 3 -> 3 Mod 5 = 3
  • F(2) = 2*F(1) + 1 = 2*3 + 1 = 7 -> 7 Mod 5 = 2
  • F(3) = 2*F(2) + 1 = 2*7 + 1 = 15 -> 15 Mod 5 = 0
  • F(4) = 2*F(3) + 1 = 2*15 + 1 = 31 -> 31 Mod 5 = 1
  • F(5) = 2*F(4) + 1 = 2*31 + 1 = 63 -> 63 Mod 5 = 3
  • 等

剰余は [1, 3, 2, 0, 1, 3, ...] であり、永久に繰り返されることに注意してください。この例から、1000 番目のエントリまでループせずに F(1000) Mod 5 を決定するにはどうすればよいでしょうか?

于 2012-06-29T15:27:51.767 に答える
0

最初に、より単純な問題を解決する方法を説明します。b がゼロであるとします。次に、 n mod Mを計算するだけです。n-1 倍する代わりに、分割統治法を使用します。

// Requires n >= 0 and M > 0.
int modularPower(int a, int n, int M) {
    if (n == 0)
        return 1;
    int result = modularPower(a, n / 2, M);
    result = (result * result) % M;
    if (n % 2 != 0)
        result = (result * a) % M;
    return result;
}

したがって、 a floor(n/2)に関してa nを計算し、それを 2 乗して、n が奇数の場合は再度 a を掛けることができます。

問題を解決するには、まず関数 f(x) = (ax + b) (mod M) を定義します。f n (1)を計算する必要があります。これは、初期値 1 に fn 回を適用することです。したがって、前の問題と同様に、分割統治法を使用できます。幸いなことに、2 つの線形関数の合成も線形です。線形関数は、3 つの整数 (2 つの定数とモジュラス) で表すことができます。線形関数と指数を取り、その回数合成された関数を返す関数を作成します。

于 2012-06-29T20:59:01.783 に答える