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 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://mirror.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