結果
問題 | No.344 ある無理数の累乗 |
ユーザー | WSKR |
提出日時 | 2020-09-23 15:58:41 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 2,153 bytes |
コンパイル時間 | 102 ms |
コンパイル使用メモリ | 10,820 KB |
実行使用メモリ | 29,844 KB |
最終ジャッジ日時 | 2023-09-10 07:15:00 |
合計ジャッジ時間 | 8,030 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 132 ms
29,736 KB |
testcase_01 | AC | 136 ms
29,692 KB |
testcase_02 | AC | 132 ms
29,660 KB |
testcase_03 | AC | 130 ms
29,760 KB |
testcase_04 | AC | 132 ms
29,756 KB |
testcase_05 | AC | 133 ms
29,828 KB |
testcase_06 | AC | 131 ms
29,772 KB |
testcase_07 | AC | 131 ms
29,728 KB |
testcase_08 | AC | 132 ms
29,760 KB |
testcase_09 | AC | 134 ms
29,636 KB |
testcase_10 | AC | 130 ms
29,788 KB |
testcase_11 | AC | 135 ms
29,732 KB |
testcase_12 | AC | 133 ms
29,720 KB |
testcase_13 | AC | 131 ms
29,728 KB |
testcase_14 | AC | 132 ms
29,772 KB |
testcase_15 | AC | 131 ms
29,772 KB |
testcase_16 | AC | 131 ms
29,720 KB |
testcase_17 | AC | 132 ms
29,744 KB |
testcase_18 | AC | 131 ms
29,688 KB |
testcase_19 | AC | 131 ms
29,744 KB |
testcase_20 | AC | 134 ms
29,716 KB |
testcase_21 | AC | 132 ms
29,720 KB |
testcase_22 | AC | 132 ms
29,772 KB |
testcase_23 | AC | 135 ms
29,760 KB |
testcase_24 | AC | 133 ms
29,652 KB |
testcase_25 | AC | 135 ms
29,724 KB |
testcase_26 | AC | 138 ms
29,820 KB |
testcase_27 | AC | 136 ms
29,844 KB |
testcase_28 | AC | 133 ms
29,820 KB |
testcase_29 | AC | 136 ms
29,784 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()