結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2022-04-25 12:40:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 81,856 KB |
実行使用メモリ | 54,596 KB |
最終ジャッジ日時 | 2024-06-27 08:09:29 |
合計ジャッジ時間 | 3,163 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
n=int(input())mod2 = 10**9+7mod1 = 2*(mod2+1)f = [[1, 1], [1, 0]]nt = nsize = 0while nt > 0:size += 1nt //= 2dp = [[[0, 0], [0, 0]] for i in range(size+1)]dp[0] = ffor i in range(size):for j in range(2):for k in range(2):for l in range(2):# f[j][l] * f[l][k]dp[i+1][j][k] += dp[i][j][l] * dp[i][l][k] % mod1dp[i+1][j][k] %= mod1#print(*dp,sep="\n")mt = [1, 0]for i in range(size+1):if (n >> i)&1:nmt = [0, 0]for k in range(2):for l in range(2):nmt[k] += dp[i][k][l] * mt[l] % mod1nmt[k] %= mod1mt[0] = nmt[0]mt[1] = nmt[1]targ = mt[1]#print(targ)nt = targsize = 0while nt > 0:size += 1nt //= 2dp = [[[0, 0], [0, 0]] for i in range(size+1)]dp[0] = ffor i in range(size):for j in range(2):for k in range(2):for l in range(2):# f[j][l] * f[l][k]dp[i+1][j][k] += dp[i][j][l] * dp[i][l][k] % mod2dp[i+1][j][k] %= mod2mt = [1, 0]for i in range(size+1):if (targ >> i)&1:nmt = [0, 0]for k in range(2):for l in range(2):nmt[k] += dp[i][k][l] * mt[l] % mod2nmt[k] %= mod2mt[0] = nmt[0]mt[1] = nmt[1]print(mt[1])