結果
問題 | No.129 お年玉(2) |
ユーザー | 👑 rin204 |
提出日時 | 2022-07-04 13:58:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 908 ms / 5,000 ms |
コード長 | 4,010 bytes |
コンパイル時間 | 179 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 106,752 KB |
最終ジャッジ日時 | 2024-05-08 03:12:16 |
合計ジャッジ時間 | 45,985 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 878 ms
106,128 KB |
testcase_01 | AC | 870 ms
106,592 KB |
testcase_02 | AC | 871 ms
106,624 KB |
testcase_03 | AC | 863 ms
106,112 KB |
testcase_04 | AC | 869 ms
106,572 KB |
testcase_05 | AC | 869 ms
106,368 KB |
testcase_06 | AC | 868 ms
106,624 KB |
testcase_07 | AC | 866 ms
106,600 KB |
testcase_08 | AC | 867 ms
106,124 KB |
testcase_09 | AC | 869 ms
106,240 KB |
testcase_10 | AC | 869 ms
106,496 KB |
testcase_11 | AC | 863 ms
106,112 KB |
testcase_12 | AC | 869 ms
106,192 KB |
testcase_13 | AC | 860 ms
106,624 KB |
testcase_14 | AC | 860 ms
106,624 KB |
testcase_15 | AC | 862 ms
106,240 KB |
testcase_16 | AC | 862 ms
106,112 KB |
testcase_17 | AC | 877 ms
106,560 KB |
testcase_18 | AC | 879 ms
106,240 KB |
testcase_19 | AC | 873 ms
106,236 KB |
testcase_20 | AC | 871 ms
106,112 KB |
testcase_21 | AC | 867 ms
106,368 KB |
testcase_22 | AC | 867 ms
106,184 KB |
testcase_23 | AC | 864 ms
106,496 KB |
testcase_24 | AC | 867 ms
105,984 KB |
testcase_25 | AC | 865 ms
106,180 KB |
testcase_26 | AC | 863 ms
106,368 KB |
testcase_27 | AC | 867 ms
105,984 KB |
testcase_28 | AC | 875 ms
106,184 KB |
testcase_29 | AC | 871 ms
106,368 KB |
testcase_30 | AC | 870 ms
106,252 KB |
testcase_31 | AC | 863 ms
106,112 KB |
testcase_32 | AC | 877 ms
105,984 KB |
testcase_33 | AC | 888 ms
105,984 KB |
testcase_34 | AC | 889 ms
106,580 KB |
testcase_35 | AC | 886 ms
106,496 KB |
testcase_36 | AC | 887 ms
106,112 KB |
testcase_37 | AC | 903 ms
106,240 KB |
testcase_38 | AC | 908 ms
106,368 KB |
testcase_39 | AC | 885 ms
106,368 KB |
testcase_40 | AC | 885 ms
105,984 KB |
testcase_41 | AC | 886 ms
106,412 KB |
testcase_42 | AC | 905 ms
106,240 KB |
testcase_43 | AC | 878 ms
106,368 KB |
testcase_44 | AC | 870 ms
105,984 KB |
testcase_45 | AC | 890 ms
106,240 KB |
testcase_46 | AC | 890 ms
106,112 KB |
testcase_47 | AC | 901 ms
106,752 KB |
testcase_48 | AC | 901 ms
106,496 KB |
ソースコード
n = int(input()) m = int(input()) n //= 1000 n %= m from math import gcd def isprime(n): if n <= 1: return False elif n == 2: return True elif n % 2 == 0: return False A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022] s = 0 d = n - 1 while d % 2 == 0: s += 1 d >>= 1 for a in A: if a % n == 0: return True x = pow(a, d, n) if x != 1: for t in range(s): if x == n - 1: break x = x * x % n else: return False return True def pollard(n): if n % 2 == 0: return 2 if isprime(n): return n f = lambda x:(x * x + 1) % n step = 0 while 1: step += 1 x = step y = f(x) while 1: p = gcd(y - x + n, n) if p == 0 or p == n: break if p != 1: return p x = 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 += right return sorted(left) def modinv(a, MOD): b = MOD u = 1 v = 0 while b: t = a // b a -= t * b u -= t * v a, b = b, a u, v = v, u u %= MOD return u def Garner(M, R): if not M: return 0 m_prod = M[0] C = R[0] for m, r in zip(M[1:], R[1:]): t = (r - C) * modinv(m_prod, m) % m C += t * m_prod m_prod *= m return C class Combination_Arbitary_sub: def __init__(self, p, pq): self.fact = [0] * (pq + 1) self.invfact = [0] * (pq + 1) self.fact[0] = 1 self.invfact[0] = 1 for 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 % pq self.invfact[i] = modinv(self.fact[i], pq) class Combination_Arbitary: def __init__(self, MOD): self.MOD = MOD primes = primefact(MOD) self.le = len(set(primes)) self.p = sorted(set(primes)) self.q = [0] * self.le self.pq = [1] * self.le ind = -1 bef = -1 for p in primes: if p != bef: bef = p ind += 1 self.q[ind] += 1 self.pq[ind] *= p self.fac = [None] * self.le for 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 - k e0 = 0 u = n // p while u > 0: e0 += u u //= p u = k // p while u > 0: e0 -= u u //= p u = z // p while u > 0: e0 -= u u //= p em = 0 u = n // pq while u > 0: em += u u //= p u = k // pq while u > 0: em -= u u //= p u = z // pq while u > 0: em -= u u //= p ret = 1 while n > 0: ret *= fac.fact[n % pq] ret %= pq ret *= fac.invfact[k % pq] ret %= pq ret *= fac.invfact[z % pq] ret %= pq n //= p k //= p z //= p ret *= pow(p, e0, pq) ret %= pq if(not(p == 2 and q >= 3) and em & 1): ret = -ret % pq return ret def nCk(self, n, k): if n < k or k < 0: return 0 R = [0] * self.le for 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))