結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | rpy3cpp |
提出日時 | 2015-08-20 00:27:13 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 337 ms / 5,000 ms |
コード長 | 3,922 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 11,296 KB |
実行使用メモリ | 9,096 KB |
最終ジャッジ日時 | 2023-09-25 13:42:34 |
合計ジャッジ時間 | 6,878 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
8,800 KB |
testcase_01 | AC | 18 ms
8,812 KB |
testcase_02 | AC | 220 ms
8,840 KB |
testcase_03 | AC | 38 ms
8,724 KB |
testcase_04 | AC | 96 ms
8,348 KB |
testcase_05 | AC | 81 ms
8,764 KB |
testcase_06 | AC | 96 ms
8,744 KB |
testcase_07 | AC | 144 ms
8,852 KB |
testcase_08 | AC | 33 ms
8,676 KB |
testcase_09 | AC | 113 ms
8,492 KB |
testcase_10 | AC | 55 ms
8,644 KB |
testcase_11 | AC | 57 ms
8,672 KB |
testcase_12 | AC | 81 ms
8,700 KB |
testcase_13 | AC | 44 ms
8,448 KB |
testcase_14 | AC | 24 ms
8,660 KB |
testcase_15 | AC | 170 ms
8,908 KB |
testcase_16 | AC | 147 ms
8,912 KB |
testcase_17 | AC | 53 ms
8,636 KB |
testcase_18 | AC | 154 ms
8,896 KB |
testcase_19 | AC | 204 ms
8,880 KB |
testcase_20 | AC | 189 ms
8,752 KB |
testcase_21 | AC | 337 ms
9,000 KB |
testcase_22 | AC | 293 ms
8,704 KB |
testcase_23 | AC | 30 ms
9,024 KB |
testcase_24 | AC | 169 ms
9,096 KB |
testcase_25 | AC | 157 ms
8,940 KB |
testcase_26 | AC | 150 ms
9,096 KB |
testcase_27 | AC | 180 ms
8,456 KB |
testcase_28 | AC | 55 ms
8,928 KB |
testcase_29 | AC | 307 ms
8,624 KB |
testcase_30 | AC | 208 ms
8,800 KB |
testcase_31 | AC | 18 ms
8,736 KB |
testcase_32 | AC | 75 ms
8,752 KB |
testcase_33 | AC | 103 ms
8,784 KB |
testcase_34 | AC | 87 ms
8,696 KB |
testcase_35 | AC | 77 ms
8,720 KB |
testcase_36 | AC | 165 ms
8,960 KB |
testcase_37 | AC | 32 ms
8,676 KB |
testcase_38 | AC | 182 ms
8,800 KB |
testcase_39 | AC | 84 ms
8,724 KB |
ソースコード
class Matrix(object): def __init__(self, nrow=1, ncol=1): self.nrow = nrow self.ncol = ncol self._data = [[0] * nrow for c in range(ncol)] def from2Dlist(self, data): self.nrow = len(data) self.ncol = len(data[0]) for row in data: if len(row) != self.ncol: raise IndexError('All column lengths must be same.') self._data = [[val for val in row] for row in data] return self def __getitem__(self, key): row, col = key return self._data[row][col] def __setitem__(self, key, value): row, col = key self._data[row][col] = value def __add__(self, other): if self.nrow != other.nrow or self.ncol != other.ncol: raise TypeError('lhs and rhs must be same size.') mat = [] for row1, row2 in zip(self._data, other._data): row = [a + b for a, b in zip(row1, row2)] mat.append(row) return Matrix().from2Dlist(mat) def __sub__(self, other): if self.nrow != other.nrow or self.ncol != other.ncol: raise TypeError('lhs and rhs must be same size.') mat = [] for row1, row2 in zip(self._data, other._data): row = [a - b for a, b in zip(row1, row2)] mat.append(row) return Matrix().from2Dlist(mat) def __mul__(self, other): '''行列の積を求める。要素毎の乗算ではない。 ''' mod = 10 ** 9 + 7 if self.ncol != other.nrow: raise TypeError('ncol of lhs and nrow of rhs must be same.') mat = [] mat2 = other._data n = other.ncol for row1 in self._data: row = [sum(a * b[i] for a, b in zip(row1, mat2)) % mod for i in range(n)] mat.append(row) return Matrix().from2Dlist(mat) def __imul__(self, other): self = self.__mul__(other) return self def __str__(self): return '\n'.join(map(str, self._data)) def read_data(): N, K = map(int, input().split()) As = list(map(int, input().split())) return N, K, As def solve(N, K, As): if K <= 10**6: return solve2(N, K, As) else: return solve3(N, K, As) def solve2(N, K, As): mod = 10**9 + 7 As.append(sum(As) % mod) idx = N cum = sum(As) % mod for i in range(1, K - N): new_idx = (idx + 1) % (N + 1) As[new_idx] = (2 * As[idx] - As[new_idx]) % mod cum += As[new_idx] cum %= mod idx = new_idx return As[idx], cum def solve3(N, K, As): mod = 10 ** 9 + 7 if K <= N: return As[K - 1] data = [[1] * N] for n in range(N-1): row = [0] * N row[n] = 1 data.append(row) dataI = [[0] * N for i in range(N)] for n in range(N): dataI[n][n] = 1 mat = Matrix().from2Dlist(data) mat2 = Matrix().from2Dlist(dataI) K = K - N while K: if K & 1: mat2 *= mat mat *= mat K >>= 1 fk = sum(mat2[0, i] * ai for i, ai in enumerate(As[::-1])) % mod mat = Matrix().from2Dlist(data) matI = Matrix().from2Dlist(dataI) mat3 = mat2 * mat - matI inv = inverse(N) inv *= mat3 sk = (sum(inv[0, i] * ai for i, ai in enumerate(As[::-1])) + sum(As[:-1])) % mod return fk, sk def inverse(n): mod = 10 ** 9 + 7 row = [i for i in range(N, 0, -1)] data = [row[:] for i in range(n)] m = n - 1 for i in range(n): for j in range(i + 1): data[i][j] -= m q = mod - 2 minv = 1 while q: if q & 1: minv *= m minv %= mod m *= m m %= mod q >>= 1 for row in data: for i in range(n): row[i] *= minv row[i] %= mod return Matrix().from2Dlist(data) N, K, As = read_data() print(*solve(N, K, As))