難易度は高くありませんが、機械的に問題を解く私に多くの思考の空間を提供しました.

質問する

00カードと1カードを使用して、タイミングで作成できるすべてのダミー数にNを数えます.
たとえば、N=1では1しか作成できませんが、N=2では00,11を作成できます.(01,10は作成できません.)また、n=4の場合、0011、0000、1001、1100、1111の計5個のバイナリ数列を作成することができる.
タイルは無限に多いと仮定します.
1 ≤ N ≤ 1,000,000
出力:すべての長さNのバイナリ数列の個数を15746で割る

解決する

DPを利用して問題を解決したが、多くの問題に直面した.
ポイント対ポイント、メモリオーバーフロー、および(改良案)swapの使用

1.点火式

Nに値を代入すれば、フィボナッチと同じ点火方式であることがわかります.しかし、これは証明ではなく、大学入学の結果から推測したもので、少し気分が悪い.
Nが偶数の場合、長さが前の偶数値(N−2)の場合、結果には00、長さが前の奇数値(N−1)の場合、結果には1を加えることができる.
Nが奇数の場合も少なくない.N−2の場合、結果物は1、N−1の場合、結果物は00であった.
したがって、a(n) = a(n-1) + a(n-2)点火式を信頼して使用することができる.

2.メモリオーバーフロー

N = int(input())
counts = [0] * 1000001
counts[1], counts[2] = 1, 2
for i in range(3, N+1):
    counts[i] = counts[i-1] + counts[i-2]
print(counts[N]%15746)

なぜ残りを15746に分けさせたのか分かりませんが、N値のためです.
Nの最大値は100万なので、メモリがたくさん消費されます.
したがって、結果値を配列に格納する場合は、残りの値を15746に分ける必要があります.

for i in range(3, N+1):
    counts[i] = (counts[i-1] + counts[i-2]) % 15746
print(counts[N])

3. SWAP

Nが100万であれば100万+1個の配列が生じる.
これもメモリをたくさん食べたようで、swapで解決できます.
この問題では、テストケース数は入力されないため、次の指定された数が配列に値を持つかどうかは不明です.
したがって,前の結果値と前の結果値を知るだけでよい.

N = int(input())
if N == 1:
    res = 1
elif N == 2:
    res = 2
else:
    a, b = 1, 2
    for i in range(3, N+1):
        a, b = b, (a+b) % 15746
        res = b
print(res)

メモリが半分以上減った.

リファレンス

https://sungmin-joo.tistory.com/21
https://www.acmicpc.net/board/view/4265