結果
問題 | No.187 中華風 (Hard) |
ユーザー | okayu29 |
提出日時 | 2023-01-31 14:59:51 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,601 ms / 3,000 ms |
コード長 | 1,609 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 11,164 KB |
実行使用メモリ | 56,156 KB |
最終ジャッジ日時 | 2023-09-13 07:57:57 |
合計ジャッジ時間 | 25,641 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
8,716 KB |
testcase_01 | AC | 20 ms
8,712 KB |
testcase_02 | AC | 1,434 ms
54,388 KB |
testcase_03 | AC | 1,426 ms
54,472 KB |
testcase_04 | AC | 1,584 ms
56,128 KB |
testcase_05 | AC | 1,583 ms
56,060 KB |
testcase_06 | AC | 1,598 ms
56,088 KB |
testcase_07 | AC | 1,585 ms
56,084 KB |
testcase_08 | AC | 1,468 ms
56,016 KB |
testcase_09 | AC | 1,458 ms
56,128 KB |
testcase_10 | AC | 1,456 ms
56,092 KB |
testcase_11 | AC | 1,585 ms
56,156 KB |
testcase_12 | AC | 1,601 ms
56,092 KB |
testcase_13 | AC | 972 ms
24,548 KB |
testcase_14 | AC | 971 ms
24,588 KB |
testcase_15 | AC | 1,299 ms
39,448 KB |
testcase_16 | AC | 1,308 ms
39,480 KB |
testcase_17 | AC | 16 ms
8,464 KB |
testcase_18 | AC | 19 ms
8,620 KB |
testcase_19 | AC | 15 ms
8,488 KB |
testcase_20 | AC | 1,219 ms
44,824 KB |
testcase_21 | AC | 16 ms
8,572 KB |
testcase_22 | AC | 1,577 ms
55,980 KB |
testcase_23 | AC | 16 ms
8,580 KB |
testcase_24 | AC | 16 ms
8,568 KB |
ソースコード
from math import gcd import sys sys.setrecursionlimit(10**6) def extgcd(a, b, x1=1, y1=0, x2=0, y2=1): if b == 0: return x1, y1 q = a//b return extgcd(b, a%b, x2 ,y2, x1-x2*q, y1-y2*q) def crt(a, m, md): a = a[:] m = m + [md] N = len(m) M = [[1]*N for i in range(N)] R = [0]*N for i in range(N): for j in range(1, i+1): M[i][j] = (M[i][j-1] * m[j-1]) % m[i] R[i] = extgcd(M[i][i], m[i])[0] % m[i] memo = [[-1]*N for i in range(N)] def rec(i, j): if i == -1: return 0 if memo[i][j] >= 0: return memo[i][j] v = (rec(i-1, j) + M[j][i]*(R[i]*(a[i]-rec(i-1, i))%m[i])) % m[j] memo[i][j] = v return memo[i][j] rec(N-2, N-1) return memo[N-2][N-1], M[N-1][N-1] def pre_garner(a, m): for i in range(len(m)): for j in range(len(m)): if i == j: continue g = gcd(m[i], m[j]) if (a[i]-a[j])%g != 0: return False m[i] //= g m[j] //= g gi = gcd(g, m[i]) gj = g//gi while g != 1: g = gcd(gi, gj) gi *= g gj //= g m[i] *= gi m[j] *= gj a[i] %= m[i] a[j] %= m[j] return True n = int(input()) a, m = zip(*(tuple(map(int, input().split())) for _ in range(n))) a, m = list(a), list(m) if not pre_garner(a, m): print(-1) exit() x = crt(a, m, 10**9+7) x, mm = x if all(ai==0 for ai in a): print(mm) else: print(x)