結果
問題 | No.344 ある無理数の累乗 |
ユーザー | WSKR |
提出日時 | 2020-09-23 15:58:41 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 529 ms / 2,000 ms |
コード長 | 2,153 bytes |
コンパイル時間 | 113 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 44,580 KB |
最終ジャッジ日時 | 2024-06-27 22:42:27 |
合計ジャッジ時間 | 18,032 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 525 ms
43,932 KB |
testcase_01 | AC | 526 ms
44,072 KB |
testcase_02 | AC | 521 ms
44,456 KB |
testcase_03 | AC | 520 ms
44,316 KB |
testcase_04 | AC | 516 ms
44,316 KB |
testcase_05 | AC | 516 ms
44,448 KB |
testcase_06 | AC | 518 ms
44,568 KB |
testcase_07 | AC | 518 ms
44,188 KB |
testcase_08 | AC | 507 ms
44,316 KB |
testcase_09 | AC | 520 ms
44,188 KB |
testcase_10 | AC | 511 ms
44,192 KB |
testcase_11 | AC | 514 ms
44,064 KB |
testcase_12 | AC | 516 ms
44,320 KB |
testcase_13 | AC | 516 ms
44,448 KB |
testcase_14 | AC | 526 ms
44,064 KB |
testcase_15 | AC | 529 ms
44,316 KB |
testcase_16 | AC | 517 ms
44,320 KB |
testcase_17 | AC | 518 ms
44,060 KB |
testcase_18 | AC | 521 ms
44,064 KB |
testcase_19 | AC | 514 ms
44,060 KB |
testcase_20 | AC | 506 ms
44,320 KB |
testcase_21 | AC | 518 ms
44,064 KB |
testcase_22 | AC | 513 ms
44,580 KB |
testcase_23 | AC | 525 ms
44,076 KB |
testcase_24 | AC | 524 ms
44,068 KB |
testcase_25 | AC | 526 ms
44,324 KB |
testcase_26 | AC | 516 ms
44,196 KB |
testcase_27 | AC | 515 ms
44,444 KB |
testcase_28 | AC | 514 ms
43,928 KB |
testcase_29 | AC | 519 ms
44,184 KB |
ソースコード
import numpy as np def find_sequence(N, Terms, coefficients, mod): #given the sequence in the form below: #[first K term] := a0,a1.......a(k-1) #[recurrence relation] := a(n+k)= b(k-1)*a(n+k-1)+....... b(0)*a(n) #Then,define Terms and coefficients as follows: #Terms := [a0....... ak] #coefficients :=[b0.....bk] # return a_n %mod in O(K**2 log N), which is much faster than matrix_binary_powering_method,which works in O(K**3 logN). #Note that mod*K<2**64 in order to avoid overflow error. assert len(Terms) == len(coefficients) K = len(coefficients) data = [N] while N: if N % 2 == 0: N = N//2 data.append(N) else: N -= 1 data.append(N) data.reverse() C = np.array([0]*K) old_C = np.array([0]*K) tmp_C = np.array([0]*K) Cs = np.array([[0]*K for _ in range(K)]) cofs = np.array(coefficients) #C(0,i) の定義 C[0] = 1 for i in range(len(data)-1): now, nex = data[i], data[i+1] old_C *= 0 old_C += C if nex == 1+now: C = old_C[K-1]*cofs C %= mod for i in range(1, K): C[i] += old_C[i-1] C %= mod continue else: for i in range(K): Cs[i] *= 0 Cs[0] += C for i in range(1, K): Cs[i] = Cs[i-1][K-1]*cofs Cs[i] %= mod for j in range(1, K): Cs[i][j] += Cs[i-1][j-1] Cs[i] %= mod C *= 0 Cs = Cs.T for i in range(K): tmp_C = 0 tmp_C = old_C*Cs[i] tmp_C %= mod C[i] = np.sum(tmp_C) C[i] %= mod ans = 0 for i in range(K): ans += Terms[i]*C[i] ans %= mod return ans def main(): N = int(input()) if N == 0: print(1) else: ans = find_sequence(N, [2, 2], [2, 2], 1000) if N%2 == 0: ans -= 1 print(ans % 1000) return if __name__ == "__main__": main()