5

CodeSprint 3 が終わった今、この問題を解決する方法を考えていました。r と n の大きな値 (0<=n<=10^9 ; 0<=r<=n) については、nCr mod 142857 を単純に計算する必要があります。組み合わせを計算するために min(r, nr) 回の反復を行う再帰的な方法を使用しました。これは十分に効率的ではないことがわかりました。いくつかの異なる方法を試しましたが、どれも十分に効率的ではないようです。助言がありますか？

4

1 に答える 1

9

非素数 mod の場合、それを因数分解 (142857 = 3^3 * 11 * 13 * 37) し、一般的なルーカスの定理を使用して mod の各素因数について C(n,k) mod p^q を計算し、次を使用してそれらを結合します。中国剰余定理。

たとえば、C(234, 44) mod 142857 = 6084 の場合、

  • C(234, 44) mod 3^3 = 9
  • C(234, 44) mod 11 = 1
  • C(234, 44) mod 13 = 0
  • C(234, 44) mod 37 = 16

中国の剰余定理では、次のような x を見つける必要があります。

  • x = 9 mod 3^3
  • x = 1 mod 11
  • x = 0 mod 13
  • x = 16 mod 37

結果は x = 6084 です。

例

C(234, 44) mod 3^3

最初に n、k、nk を基数 p に変換します

n = 234_10 = 22200_3

k = 44_10 = 1122_3

r = nk = 190_10 = 21001_3

次にキャリー数を求めます

e[i] = number of carries from i to end
e   4 3 2 1 0
        1 1
r   2 1 0 0 1
k     1 1 2 2
n   2 2 2 0 0

次に、一般的なルーカスに必要な階乗関数を作成します

def f(n, p):
    r = 1
    for i in range(1, n+1):
        if i % p != 0:
            r *= i
    return r

q = 3 であるため、一度にベース p 表現の 3 桁のみを考慮します。

そう

f(222_3, 3)/[f(210_3, 3) * f(011_3, 3)] *
f(220_3, 3)/[f(100_3, 3) * f(112_3, 3)] *
f(200_3, 3)/[f(001_3, 3) * f(122_3, 3)] = 6719344775 / 7

今

s = 1 if p = 2 and q >= 3 else -1

それで

p^e[0] * s * 6719344775 / 7 mod 3^3
e[0] = 2
p^e[0] = 3^2 = 9
s = -1
p^e[0] * s * 6719344775 = -60474102975

今、あなたは持っています

-60474102975 / 7 mod 3^3

これは線形合同であり、次のように解くことができます。

ModularInverse(7, 3^3) = 4
4 * -60474102975 mod 27 = 9

したがって、C(234, 44) mod 3^3 = 9

于 2012-11-03T17:52:14.493 に答える