Supersonic domino tilings
C

A straightforward implementation...

#include&lt;stdio.h&gt;
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0;
char r[100130];
void w(i,x,o){
    int j,k;
    j=(1&lt;&lt;b)-1&amp;~x;
    if(i&lt;a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&amp;j/2&amp;-o;j=k&amp;-k;k&amp;=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j)
        if(countonly)
            m++;
        else{
            if(c==b)
                for(k=0;k&lt;b;r[k++,l++]=10)
                    for(j=0;j&lt;a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
            else
                for(j=0;j&lt;a;r[j++,l++]=10)
                    for(k=0;k&lt;b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
            r[l++]=10;
            if(l&gt;=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&amp;a,&amp;b,&amp;countonly);
    c=b;
    if(a&lt;b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    w(0,0,1);
    if(countonly)
        printf("%llu\n",m);
    else if(l)
        fwrite(r,l,1,stdout);
}


The cheating version

#include&lt;stdio.h&gt;
#include&lt;string.h&gt;
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0,d[256];
char r[100130];
void w2(){
    int i,j,k,x;
    memset(d,0,sizeof d);
    d[0]=1;
    j=0;
    for(i=0;i&lt;a-1;i++){
        for(k=1;k&lt;(1&lt;&lt;(b-1));k*=2)
            for(x=0;x&lt;(1&lt;&lt;(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1&lt;&lt;b)-1;
    }
    for(x=0;x&lt;(1&lt;&lt;b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1&lt;&lt;b)-1)^j];
    printf("%llu\n",m);
}

void w(i,x,o){
    int j,k;
    j=(1&lt;&lt;b)-1&amp;~x;
    if(i&lt;a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&amp;j/2&amp;-o;j=k&amp;-k;k&amp;=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j){
        if(c==b)
            for(k=0;k&lt;b;r[k++,l++]=10)
                for(j=0;j&lt;a;j++)
                    r[l++]=45+79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
        else
            for(j=0;j&lt;a;r[j++,l++]=10)
                for(k=0;k&lt;b;k++)
                    r[l++]=124-79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
        r[l++]=10;
        if(l&gt;=100000){
            fwrite(r,l,1,stdout);
            l=0;
        }
    }
}

int main(){
    scanf("%d %d %d",&amp;a,&amp;b,&amp;countonly);
    c=b;
    if(a&lt;b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    if(countonly)
        w2();
    else{
        w(0,0,1);
        if(l)
            fwrite(r,l,1,stdout);
    }
}


Explanation of the faster algorithm

It scans from left to right, and maintain the state d[i][j], where:


i is in [0,m), which means the current column.
j is a bit vector of size n, where the bit would be 1 if the corresponding position in column i is already occupied before starting working on this column. I.e. it is occupied by the right half of a --.
d[i][j] is the total number of different tilings.


Then say e[i][j] = the sum of d[i][k] where you can put vertical dominoes base on k to form a j. e[i][j] would be the number of tilings where each 1 bit in j is occupied by anything but the left half of a --. Fill them with -- and you'll get d[i+1][~j] = e[i][j]. e[m-1][every bit being 1] or d[m][0] is the final answer.

A naive implementation will get you the time complexity somewhere near g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n) (already fast enough if n=m=8). But you can instead firstly loop for each possible domino, and try to add it to every tiling that can have this domino added, and merge the result to the original array d (like the algorithm for the Knapsack problem). And this becomes O(n*2^n). And everything else are implementation details. The whole code runs in O(m*n*2^n).