2013-team5/andrew/13/I

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> PLL;
const int INF=1e8, MN=1e6+7;
int n,m;
LL f[20][1<<8][1<<7];

void dfs(int i,int mask,int s,int newmask,int news,int d){
    if (d>=m){
        f[i+1][newmask][news]+=f[i][mask][s];
        return;
    }
    int qd=news|(s&(1<<d));
    int qx=news|(s&(1<<(d+1)));
    if ((mask>>d)&1) dfs(i,mask,s,newmask,qd,d+1);
    else{
        if (d+1<m && !((mask>>(d+1))&1))
            dfs(i,mask,s,newmask,qx,d+2);
        dfs(i,mask,s,newmask|(1<<d),qd,d+1);
    }
}

int main(){
    freopen("solid.in","r",stdin);
    freopen("solid.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (n<m) swap(n,m);
    int tmp=(1<<(m-1))-1;
    f[0][0][tmp]=1;
    dfs(0,0,tmp,0,0,0);
    for (int i=1; i<n; i++)
        for (int mask=1; mask<(1<<m); mask++)
            for (int s=0; s<(1<<(m-1)); s++)
                if (f[i][mask][s]) dfs(i,mask,s,0,0,0);
    printf("%I64d\n",f[n][0][0]);
    return 0;
}
}}}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> PLL;
const int INF=1e8, MN=1e6+7;
int n,m;
LL f[20][1<<8][1<<7];
void dfs(int i,int mask,int s,int newmask,int news,int d){
    if (d>=m){
        f[i+1][newmask][news]+=f[i][mask][s];
        return;
    }
    int qd=news|(s&(1<<d));
    int qx=news|(s&(1<<(d+1)));
    if ((mask>>d)&1) dfs(i,mask,s,newmask,qd,d+1);
    else{
        if (d+1<m && !((mask>>(d+1))&1))
            dfs(i,mask,s,newmask,qx,d+2);
        dfs(i,mask,s,newmask|(1<<d),qd,d+1);
    }
}
int main(){
    freopen("solid.in","r",stdin);
    freopen("solid.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (n<m) swap(n,m);
    int tmp=(1<<(m-1))-1;
    f[0][0][tmp]=1;
    dfs(0,0,tmp,0,0,0);
    for (int i=1; i<n; i++)
        for (int mask=1; mask<(1<<m); mask++)
            for (int s=0; s<(1<<(m-1)); s++)
                if (f[i][mask][s]) dfs(i,mask,s,0,0,0);
    printf("%I64d\n",f[n][0][0]);
    return 0;
}