Large nCr Small Modulus(Easy)

2 secs 1024 MB

本問では制約上、 $M$ の素因数の指数が $1$ と保証されています。
そのため各素因数ごとにLucasの定理で $\binom{N}{R}$ $mod$ $P_i$ を計算し、中国剰余定理で解を復元すればよいです。
計算量は前計算 $O(M)$ ・二項係数の計算に $O(logNlogM + logM)$ です。
内訳は以下の通りです。

階乗の前計算に $O(ΣP_i) \leq O(ΠP_i) = O(M)$ 時間・空間
素因数ごとの二項係数の計算に $O(Σlog_{P_i} N) \leq O(logNlogM)$ 時間・空間
中国剰余定理に $O(Σlog P_i) = O(logM)$ 時間

なお本問の制約範囲外ですが、抽象化の際には $N,R = 0$ や $N < R$ 、 $M = 1$ のケースに注意してください。

解答例(Python)

解答例では、二項係数が与えられるたびに階乗を計算しています。

解答例

xxxxxxxxxx
 
n,r,m = map(int,input().split())
c = int(input())
p = list(map(int,input().split()))
e = list(map(int,input().split()))
​
#convert x-adic number
def convert(n,x):
    a = []
    while n > 0:
        a.append(n % x)
        n //= x
    return a + [0]
​
#calculate smallest n: n ≡ x1 mod y1 ≡ x2 mod y2
def CRT(x1, y1, x2, y2):
    a = (x2 - x1) * pow(y1, -1, y2) % y2
    return a * y1 + x1
​
#calculate nCr mod prime
def Lucas_theorem(n,r,p):
    f = [1] * p
    for i in range(2, p):
        f[i] = f[i - 1] * i % p
    ans = 1
    for x,y in zip(convert(n,p), convert(r,p)):
        if x < y:
            return 0
        ans *= f[x] * pow(f[y] * f[x - y] % p, -1, p) % p
        ans %= p
    return ans
​
lucas = [Lucas_theorem(n,r,prime) for prime in p]
ans,mod = 0,1
for rem,prime in zip(lucas,p):
    ans = CRT(ans, mod, rem, prime)
    mod *= prime
print(ans)

Large nCr Small Modulus(Easy)

解説

解答例(Python)

解答例