[アルゴリズム]白準-01タイル

白駿-01タイル

説明する

N = int(input())
MOD = 15746

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
for i in range(5, 1000001):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[N])

似たようなdp問題をたくさん解いたので、簡単に解けました.しかし、dp問題を久しぶりにやったせいか、十分な根拠が確立されていないので探してみました.
解説
まず長さがi因数をもたらすことを考えてみましょう.では、使えるデジタルカードは00と1です.つまり、以前に作成した数字に00を付けたり、1を付けたりします.でもよく考えると00の長さが2なのでi-1には貼れませんしたがって、i−2に00を貼り付ける場合とi−1に1を貼り付けることができる場合との和である.
しかし、ここで質問することもできます.なぜi-2に1を2つ追加することを考えないのですか?
その原因はi−1と1が重なることである.N=5を作成するための簡単な実験をしてみましょう.
N=3は、->00100111を表す.
N=4は、->0011、0000、1001、1100、1111を表す
まず、n−2の場合(n=3)の数に、00を加算可能な数は000100100000111100、1~2を加算した数は1100100111111の計8個である.
今回N−1であれば(N=4)の数に1を加えて作成可能な数を求めて100110011100001110111101111の計7個である.
しかし、私たちが気づいたように、かなりの重複数があります.ここで、重複データをすべて削除すると、真値は8つになります.しかし、これらの数字をすべて考慮すると、重複を解消するのは容易なことではありません.
だからN-2に100万を貼ってN-1に1を貼ってそして数を加算するとき、N-2の数に「最後」00、N-1の数に「一番前」1を加算するルール.
N-2の末尾に00を追加->00100000011100
N-1の先頭に1->100111000010011100111111を追加
これにより,合計8つの重複データが消去されると,その値が自然に見られる.
[ソース][規格]1904-01タイル|著者occidere