Help with dp on a broken profile

Revision en4, by VladKov, 2019-11-20 06:16:46

The problem of "Domino coating." It is required to find the number of ways to fill the table n * m with dominoes 2 * 1, 1 * 2. On e-maxx I found the following code. (http://e-maxx.ru/algo/profile_dynamics)   I think the asymptotic is O (n * m * 2 ^ (2n)), since in the worst case calc will be called 2 times in range n. But the comments say O (n * m * 2 ^ n). What is the correct asymptotic behavior? Works fast.

And I can not understand dp on a broken profile. I read the theory about increasing profiles in 2n, due to the appearance of a break point from 1 to n, and an additional bit in the mask. However, the code was not found anywhere. I found such code on codeforces, and something tells me that this is dp on a broken profile. (https://codeforces.com/gym/100124/submission/2804558)

I can’t understand why profiles (1 << n) and not (2 << n), what is j then, and why when calculating the mask of the next column do we add the result to the same column? I am grateful to everyone

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian VladKov 2019-11-20 07:34:44 32
en4 English VladKov 2019-11-20 06:16:46 6 Tiny change: ' times in n. But t' -> ' times in range n. But t'
en3 English VladKov 2019-11-20 06:10:49 0 (published)
en2 English VladKov 2019-11-20 06:10:29 3 Tiny change: 'Works fast\n And I c' -> 'Works fast.\n\n And I c' (saved to drafts)
en1 English VladKov 2019-11-20 06:09:41 1028 Initial revision for English translation
ru7 Russian VladKov 2019-11-20 06:02:36 41
ru6 Russian VladKov 2019-11-20 04:35:57 89
ru5 Russian VladKov 2019-11-20 04:34:12 60
ru4 Russian VladKov 2019-11-20 04:33:38 71
ru3 Russian VladKov 2019-11-20 04:32:55 2 Мелкая правка: 'явления мечта излома ' -> 'явления места излома '
ru2 Russian VladKov 2019-11-20 04:31:50 53
ru1 Russian VladKov 2019-11-20 04:30:27 960 Первая редакция (опубликовано)