ivan the fool and the probability theory - codeforces 594 c

#フィボナッチ

There is an English description below.

盤面が1行n列のときを考える
Bで塗るとき, 手前2つがBBならBで塗れない
それ以外なら塗れる
すなわち, 手前がWまたは2つ前がWのときBで塗れる

n = 7で実験
フィボナッチ数列っぽい
まぁ, そうか

int n;
cin >> n;
vector<vector<int> > dp(n, vector<int>(2));
rep(j, 2) dp[0][j] = 1;
rep(j, 2) dp[1][j] = 2;
rep3(i, 2, n) rep(j, 2) dp[i][j] = dp[i - 1][j ^ 1] + dp[i - 2][j ^ 1];
rep(j, 2) { rep(i, n) cout << dp[i][j] << " "; cout << endl; }

7
1 2 3 5 8 13 21 
1 2 3 5 8 13 21

ここで, 一角を
BB
W?
としたとします
?はWに一意に決まります

BW
W?
とすると, ?はBに一意に決まります

角の3つを, それらで矛盾がないようにどう決めても, ?は一意に決まります

よって, 一角とそれを含む縁の2辺を決めれば常に
BB
W?
の, ?のような場所ができるので一意に決まっていきます

さて, 1つの辺の決め方はフィボナッチ数列Fでした
よって答えは(F[n] + F[m] - 1) * 2です
$- 1$ : 一角が被ってる
$* 2$ : WとB

参考
https://www.cnblogs.com/wrjlinkkkkkk/p/11713316.html
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12215254132

English description

Firstly, let's think about 1 column n row grid.
When we paint a square black, if both 2 squares before the square is black, we can't paint the square black.
Otherwise, we can the square black.
In other words, if the previous square is white or the square before last is white, we can paint the square black.

The number sequence is fibonacci series.

If we paint the corner
WW
B?
? is B uniquely.

If we paint the corner
BW
W?
? is B uniquely.

If the corner is not a fobidden pattern like
BB
B?
? is uniquely determined.

To sum up, when we paint a corner and paint a row and a column including the corner, all squares are determined uniquely, because there is always a square corresponds to ?.

The answer is (F[n] + F[m] - 1) * 2.
F means fibonacci.
$-1$ is for the duplicated corner.
$*2$ is for B and W.