# URAL 1519. Formula 1

### Brief description :

（1 <= n, m <= 12 ...）

### Analyse :

• 左插头吃左插头会把右边的插头所对应的那个右插头变成左插头 ..#>.
• 右插头吃右插头会把左边的插头所对应的那个左插头变成右插头 …….

.
….

```#include
#include
#include
#include
using namespace std;   //15511 ...
const int hh = 12, ww = 12, _W = 16, ll = 15511;

long long f[2][ll], d; map H;
int L[ll], O[hh], h, w, up, l;
int s, o, n, m, p, q; int i;

#define _Pl (s & (1 << l))
#define _Pr (s & (1 << r))
#define _Pi (s & (1 << i))
// Check Plug.

#define _Ol (o & (1 << l))
#define _Or (o & (1 << r))
// Check Obstacle...

#define _Tl (s & (1 << l + _W))
#define _Tr (s & (1 << r + _W))
#define _Ti (s & (1 << i + _W))
// Return Plug Type ..

#define _Sl s ^= 1 << l
#define _Sr s ^= 1 << r
// Reset Plug ..

#define _Cl s ^= 1 << (l + _W)
#define _Cr s ^= 1 << (r + _W)
#define _Ci s ^= 1 << (i + _W)
// Change Brace Structure

inline int countBits(int x){
x = (x & 0x00005555) + ((x & 0x0000aaaa) >> 1);
x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);
x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);
x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);
return x;
}

void eatLeft(int i){
int An = 0;
for (i--;;i--){
if (!_Pi) continue;
if (_Ti) An++;
else {if (An==0){_Ci; return;} An--;}
}
}
void eatRight(int i){
int An = 0;
for (i++;;i++){
if (!_Pi) continue;
if (!_Ti) An++;
else {if (An==0){_Ci; return;} An--;}
}
}

void dfs(int l){
if (l == m){
f[p][H[s]] += d;
}
else {
int r = l + 1;

if (_Ol){
dfs(r);
return;
}

int c = s;

if (_Pl){
// 0: Stable ..
dfs(r);

if (_Tl){
// 2: Move_Right with ')' . ..
while (!_Pr && !_Or){
_Sl; _Cl; _Sr; _Cr; dfs(++r); s = c;
}

// 4: Merge with '))'
if (_Pr){
if (_Tr){
eatLeft(l); _Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;
}
// 4: Merge with ')('
else {
_Sl; _Cl; _Sr; dfs(r+1); s = c;
}
}
}
else {
// 2: Move_Right with '(' . ..
while (!_Pr && !_Or){
_Sl; _Sr; dfs(++r); s = c;
}

// 4: Merge with '(('
if (!_Or){
if (!_Tr){
eatRight(r); _Sl; _Sr; dfs(r+1); s = c;
}
// 4 Merge with '()'
else {
//!..#>..#>.f
if (i + 1 == h && r + 1 == m && countBits(s)==2){
f[p][0] += d;
}

}
}
}

}
else {
// 3: Bown a pair of new plug . ...
while (!_Pr && !_Or){
_Sl; _Sr; _Cr; dfs(++r); s = c;
}

// 1 Move_Left
if (!_Or){
if (_Tr) {_Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;}
else {_Sl; _Sr; dfs(r+1); s = c;}
}
}
}
}

void scan(int i, int ln, int rn){
while (!_Pi) i++;

if (i==w) {
H[s ^ up] = l;
L[l++] = s ^ up;
}
else {
if (ln < n) scan(i+1, ln+1, rn);
if (rn < ln) {_Ci; scan(i+1, ln, rn+1); _Ci;}
}
}

void init(){
scanf("%d%d", &h, &w);

l = 0, up = 1 << w, H.clear();
for (int i = 0; i < up; i++){
n = countBits(i);
if ((n&1)==0){s = i | up, n >>= 1, scan(0, 0, 0);}
}

char t;
for (int i = 0; i < h; i++){
O[i] = 1;
for (int j = 0; j < w; j++){
scanf(" %c", &t); O[i] <<= 1;
if (t!='.') O[i] += 1;
}
}

while (O[h-1] == 2 * up - 1) h--;
memset(f, 0, sizeof(f));
}

void solve(){
i = 0;
while (O[i] == 2 * up - 1) i++;
f[q = 0][s = 0] = d = 1; p = 1, m = w, o = O[i];
while (o & (1 << (m - 1))) m--;
dfs(0);

for (i ++; i < h; i ++){
q = p, p = 1 - p, m = w, o = O[i];
memset(f[p], 0, sizeof(f[p]));
while (o & (1 << (m - 1))) m--;
for (int ii = 0; ii < l; ii ++){
if (f[q][ii] && !(L[ii] & o))
d = f[q][ii], s = L[ii], dfs(0);
}
}
}

int main(){
//freopen("in.txt", "r", stdin);
init();  solve(); //patch();
cout << f[p][0] << endl;
}
```
```#include
#include
#include
using namespace std;
const int hh = 12, ww = 12, _W = 16, MaxH = 15511;
bool O[hh+1][ww+1]; bool A, B, X, Y; int h, w, l, s;
long long ans, d;

struct hashTable {
long long key[MaxH];

inline void clear() {
sz = 0;
}
inline void insert(int s) {
int x = s % MaxH;
for ( int it = head[x] ; it != -1 ; it = next[it] ) {
if ( state[it] == s ) {
key[it] += d;
return;
}
}
state[sz] = s, key[sz] = d;
}
} H[2] , *src , *des;

inline int countBits(int x){
x = (x & 0x00005555) + ((x & 0x0000aaaa) >> 1);
x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);
x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);
x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);
return x;
}

int eatLeft(int s, int i){
int An = 0;
for (i--;;i--){
if (!(s & (1 << i))) continue;
if (s & (1 << _W + i)) An++;
else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
}
}
int eatRight(int s, int i){
int An = 0;
for (i++;;i++){
if (!(s & (1 << i))) continue;
if (!(s & (1 << _W + i))) An++;
else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
}
}

bool _O(){
for (int i=0;iclear(), des->insert(0);
ans = 0;

int _w = w;

for (int i = 0; i < h; i ++){

for (int j = 0; j < src->sz; j ++)
des->state[j] <<= 1;

w = _w;

while (O[i][w-1]) w--;

for (int j = 0; j < w; j ++){

if (O[i][j]) continue;

swap(src, des), des->clear();

for (int k = 0; k < src->sz; k ++){
s = src->state[k], d = src->key[k];
A = s & (1 << j), B = s & (1 << (j+1));

if (!A && !B){
if (!O[i+1][j] && !O[i][j+1]) des->insert(s ^ (3 << j | 1 <<( _W + j + 1)));
}
else{

X = s & (1 << (_W + j)), Y = s & (1 << (_W + j + 1));

if (A && B){

if (X){
if (Y){ //'))'
des->insert(eatLeft(s, j) ^ (3 << j | 3 << _W + j));
}
else { //')('
des->insert(s ^ (3 << j | 1 << _W + j));
}
}
else {
if (Y){ //'()'
if (i + 1 == h && j + 1 == w && countBits(s)==2)
ans += d;
}
else { //'(('
des->insert(eatRight(s, j+1) ^ (3 << j));
}
}

}
else {
if (A){
if (!O[i+1][j]) des->insert(s);

if (!O[i][j+1]) {
if (X) des->insert(s ^ (3 << j | 3 << (_W + j)));
else des->insert(s ^ (3 << j));
}
}
else {
if (!O[i][j+1]) des->insert(s);
if (!O[i+1][j]) {
if (Y) des->insert(s ^ (3 << j | 3 << (_W + j)));
else des->insert(s ^ (3 << j));
}
}
}
}

}
}
}
}

int main(){
//freopen("in.txt", "r", stdin);
init();  solve();
cout << ans << endl;
}

/*

12 12
............
............
............
............
............
............
............
............
............
............
............
............

1076226888605605706

*/
```