BOJ 190401タイル

https://www.acmicpc.net/problem/1904
時間0.75秒、メモリ256 MB
input :

N(1 ≤ N ≤ 1,000,000)

output :
すべてのバイナリ数列(

N)の個数を15746で割る、残りの出力は

である.
条件:

N=1の場合は1しか作成できませんが、N=2の場合は00,11を作成できます.(01,10は作成できません.)N=4の場合は5個の2進数列

、例えば0011、0000、1001、1100、1111
DP[i]=DP[i-1]+DP[i-2]のルールです.
2 nはタイルを打つ時と同じです.
バイナリ1を追加します.
バイナリ数00を追加する場合に分けられます.
この問題では100万個しか作らないので、残りは後で計算します.
メモリオーバーフロー、タイムアウトが発生しました.
まずメモリを減らすために,2つの変数のみを格納し,交換のように計算を行う.

previous = 1
current = 2

temp = previous
previous = current
current = previous + temp
でも.残りの計算も時間がかかるようです.
現在=(preved+temp)%15746.


1.862.11秒の間に表示されます.
current=preved+tempで計算すると、最後に出力するときに残りの値を求めますか?


この違いがあるので、残りの計算は数字を計算するときに一緒にしましょう.
正しいコード:

import sys

n = int(sys.stdin.readline())
previous = 1
current = 2

for i in range(1, n):
    temp = previous
    previous = current
    current = (current + temp) % 15746

print(previous)