結果
問題 | No.129 お年玉(2) |
ユーザー |
👑 |
提出日時 | 2022-07-04 13:58:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 892 ms / 5,000 ms |
コード長 | 4,010 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 106,636 KB |
最終ジャッジ日時 | 2024-12-14 03:09:19 |
合計ジャッジ時間 | 45,852 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
n = int(input())m = int(input())n //= 1000n %= mfrom math import gcddef isprime(n):if n <= 1:return Falseelif n == 2:return Trueelif n % 2 == 0:return FalseA = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]s = 0d = n - 1while d % 2 == 0:s += 1d >>= 1for a in A:if a % n == 0:return Truex = pow(a, d, n)if x != 1:for t in range(s):if x == n - 1:breakx = x * x % nelse:return Falsereturn Truedef pollard(n):if n % 2 == 0:return 2if isprime(n):return nf = lambda x:(x * x + 1) % nstep = 0while 1:step += 1x = stepy = f(x)while 1:p = gcd(y - x + n, n)if p == 0 or p == n:breakif p != 1:return px = f(x)y = f(f(y))def primefact(n):if n == 1:return []p = pollard(n)if p == n:return [p]left = primefact(p)right = primefact(n // p)left += rightreturn sorted(left)def modinv(a, MOD):b = MODu = 1v = 0while b:t = a // ba -= t * bu -= t * va, b = b, au, v = v, uu %= MODreturn udef Garner(M, R):if not M:return 0m_prod = M[0]C = R[0]for m, r in zip(M[1:], R[1:]):t = (r - C) * modinv(m_prod, m) % mC += t * m_prodm_prod *= mreturn Cclass Combination_Arbitary_sub:def __init__(self, p, pq):self.fact = [0] * (pq + 1)self.invfact = [0] * (pq + 1)self.fact[0] = 1self.invfact[0] = 1for i in range(1, pq + 1):if i % p == 0:self.fact[i] = self.fact[i - 1]else:self.fact[i] = self.fact[i - 1] * i % pqself.invfact[i] = modinv(self.fact[i], pq)class Combination_Arbitary:def __init__(self, MOD):self.MOD = MODprimes = primefact(MOD)self.le = len(set(primes))self.p = sorted(set(primes))self.q = [0] * self.leself.pq = [1] * self.leind = -1bef = -1for p in primes:if p != bef:bef = pind += 1self.q[ind] += 1self.pq[ind] *= pself.fac = [None] * self.lefor i, (p_, pq_) in enumerate(zip(self.p, self.pq)):self.fac[i] = Combination_Arbitary_sub(p_, pq_)def C(self, n, k, p, q, pq, fac):z = n - ke0 = 0u = n // pwhile u > 0:e0 += uu //= pu = k // pwhile u > 0:e0 -= uu //= pu = z // pwhile u > 0:e0 -= uu //= pem = 0u = n // pqwhile u > 0:em += uu //= pu = k // pqwhile u > 0:em -= uu //= pu = z // pqwhile u > 0:em -= uu //= pret = 1while n > 0:ret *= fac.fact[n % pq]ret %= pqret *= fac.invfact[k % pq]ret %= pqret *= fac.invfact[z % pq]ret %= pqn //= pk //= pz //= pret *= pow(p, e0, pq)ret %= pqif(not(p == 2 and q >= 3) and em & 1):ret = -ret % pqreturn retdef nCk(self, n, k):if n < k or k < 0:return 0R = [0] * self.lefor i in range(self.le):R[i] = self.C(n, k, self.p[i], self.q[i], self.pq[i], self.fac[i])return Garner(self.pq, R)Comb = Combination_Arbitary(10 ** 9)print(Comb.nCk(m, n))