I think there is a O(N * M * 2^N) solution for this problem. DP[i][j][p] = solution where we currently start at point (i, j) and the first i-bits of p belongs to the (j + 1)-column and the rest of the bits belongs to the j-column. And transitions are similar to the last solution. This utilizes the 2^N different values of p and q more efficiently (since in the other solution, p cannot have zero bit before the last set bit, and q cannot have set bit after the row we currently stand in).

https://vjudge.net/problem/22385/origin

how to solve this

Thanks you very much

Is the blog still available? I have trouble with your link.

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).

Auto comment: topic has been updated by evilbuggy (previous revision, new revision, compare).