結果
問題 | No.187 中華風 (Hard) |
ユーザー | okayu29 |
提出日時 | 2023-01-31 13:39:46 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,334 bytes |
コンパイル時間 | 100 ms |
コンパイル使用メモリ | 10,780 KB |
実行使用メモリ | 56,712 KB |
最終ジャッジ日時 | 2023-09-13 07:06:31 |
合計ジャッジ時間 | 19,276 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
9,032 KB |
testcase_01 | AC | 24 ms
9,056 KB |
testcase_02 | AC | 1,036 ms
54,768 KB |
testcase_03 | AC | 1,021 ms
54,948 KB |
testcase_04 | AC | 1,182 ms
56,712 KB |
testcase_05 | AC | 1,182 ms
56,616 KB |
testcase_06 | AC | 1,182 ms
56,564 KB |
testcase_07 | AC | 1,182 ms
56,580 KB |
testcase_08 | AC | 1,057 ms
56,648 KB |
testcase_09 | AC | 1,065 ms
56,656 KB |
testcase_10 | AC | 1,056 ms
56,556 KB |
testcase_11 | AC | 1,187 ms
56,588 KB |
testcase_12 | AC | 1,189 ms
56,568 KB |
testcase_13 | AC | 669 ms
25,156 KB |
testcase_14 | AC | 666 ms
25,156 KB |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 20 ms
8,864 KB |
testcase_18 | AC | 22 ms
9,012 KB |
testcase_19 | AC | 20 ms
8,964 KB |
testcase_20 | AC | 914 ms
45,336 KB |
testcase_21 | AC | 20 ms
8,848 KB |
testcase_22 | AC | 1,190 ms
56,636 KB |
testcase_23 | AC | 20 ms
8,852 KB |
testcase_24 | AC | 20 ms
8,964 KB |
ソースコード
from math import gcd from functools import * 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[:] N = len(m) for i in range(N): for j in range(N): if i == j: continue g = gcd(m[i], m[j]) if (a[i]-a[j])%g != 0: return None m[i] //= g a[i] %= m[i] m.append(md) N += 1 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] n = int(input()) a, m = zip(*(tuple(map(int, input().split())) for _ in range(n))) a, m = list(a), list(m) x = crt(a, m, 10**9+7) if x is None: print(-1) exit() x, mm = x if all(ai==0 for ai in a): print(mm) else: print(x)