打表大法好！

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
string f[25][25]=
{{"1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"},
{"1","2","2","2","2","2","2","2","2","2","2","2","2","2","2","2","2","2","2","2"},
{"1","2","0","4","0","8","0","16","0","32","0","64","0","128","0","256","0","512","0","1024"},
{"1","2","4","12","28","74","184","472","1192","3034","7692","19540","49588","125906","319600","811376","2059728","5228914","13274132","33698012"},
{"1","2","0","28","0","308","0","3392","0","37368","0","411664","0","4535088","0","49960704","0","550391072","0","6063371968"},
{"1","2","8","74","308","2144","10640","65350","350588","2048056","11337384","64927604","363943696","2067834700","11648952596","65978136324","372421332936","2106698788256","11900935030208","67287082416580"},
{"1","2","0","184","0","10640","0","602768","0","34132984","0","1933312268","0","109512147164","0","6203392139840","0","351396413556636","0","19905156313629048"},
{"1","2","16","472","3392","65350","602768","9277152","98966276","1363456408","15674553804","204566478858","2441465049952","31026134376016","377240578987836","4731428340594028","58060619271410108","723499756992159556","8918793365733841068","110782338511967959110"},
{"1","2","0","1192","0","350588","0","98966276","0","27833987564","0","7827575547072","0","2201662329939728","0","619313040592944136","0","174213900542085378064","0","49007159454365867061516"},
{"1","2","32","3034","37368","2048056","34132984","1363456408","27833987564","934520913216","21509595448248","656152951318066","16182626220743584","467954797441974568","12004085992032768720","336871945813501053908","8836237773975508683540","243826792152688437860090","6476705240872799497024216","177029033285148340652006844"}};
signed main(){
    int n,m;cin>>n>>m,cout<<f[n-1][m-1];
    return 0;
}

参考陈丹琦的论文：https://cs.stanford.edu/~danqi/misc/dynamic-programming.pdf

个人喜欢叫这类DP为拼图DP，本质上就是把整个图看成一块块碎片拼起来的，我们DP的过程就是枚举应该放哪块碎片的过程。
至于轮廓线（逐格枚举）应该是一种优化方法，只保存有用的信息。

因为我现学现用，代码大改动了好几次，踩了不少坑。
一开始直接把格子种类当状态 状态数 6^10级别（其实因为还要记录连通性，所以比这个级别更大，但是我一开始没想到）
改成括号匹配后 3^10级别

1.换行的时候编码要偏移
2.决策的时候要复原
3.弄清楚答案是哪些状态的数值累加起来的
4.hash数组开大
5.不直接枚举，改成bfs扩展，减少无效状态
6.高精度

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

const int SIZE=177147+10;
int n,m;
int a[21];
int p[21][2];
int tmp[21];
int ha[SIZE];
int now;
int r,c;
ll state[2][SIZE];
ll num[2];
struct bignum {
    int len;
    int a[51];
    bignum() {
        len=0;
        memset(a,0,sizeof a);
    }
    void operator=(bignum x) {
        len=x.len;
        FOR(i,len) a[i]=x.a[i];
    }
    void operator=(ll x) {
        memset(a,0,sizeof a);
        while (x) {
            a[++len]=x%10;
            x/=10;
        }
        len=max(len,1);
    }
    bignum operator+(bignum x) {
        bignum res;
        res.len=max(len,x.len);
        FOR(i,res.len) {
            res.a[i]+=a[i]+x.a[i];
            res.a[i+1]+=res.a[i]/10;
            res.a[i]%=10;
        }
        if (res.a[res.len+1]) ++res.len;
        return res;
    }
    void operator+=(bignum x) {
        (*this)=(*this)+x;
    }
};
bignum f[2][SIZE];
bignum ans;
void decode(ll x) {
    memset(a,0,sizeof a);
    int cnt=0;
    while (x) {
        a[++cnt]=x%3;
        x/=3;
    }
    stack<int> s;
    memset(p,0,sizeof p);
    
    FOR(i,n+1) {
        if (a[i]==1) {
            s.push(i);
        } else if (a[i]==2) {
            p[i][0]=s.top();
            p[s.top()][1]=i;
            s.pop();
        }
    }
}
ll encode() {
    if (c==n) for (int i=n+1;i>=1;i--) a[i]=a[i-1];
    ll res=0;
    for (int i=n+1;i>=1;i--) res=res*3+a[i];
    return res;
}
void add(int now,ll code,bignum val) {
    ll tmp=code;
    code%=SIZE;
    while (ha[code]!=-1&&state[now][ha[code]]!=code) {
        ++code;
        code%=SIZE;
    }
    if (ha[code]==-1) {
        ha[code]=++num[now];
        state[now][ha[code]]=tmp;
        f[now][ha[code]]=val;
    } else {
        f[now][ha[code]]+=val;
    }
}
void print(bignum x) {
    for (int i=x.len;i>=1;i--) cout<<x.a[i];
    cout<<endl;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>m>>n;
    if (n==1||m==1) {
        cout<<1<<endl;
        return 0;
    }
    if (n>m) swap(m,n);
    ans=0;
    num[1]=1,ha[0]=1,state[1][1]=0,f[1][1]=1;
    for (r=1;r<=m;r++) for(c=1;c<=n;c++) {
        now^=1;
        memset(f[now^1],0,sizeof f[now^1]);
        memset(ha,-1,sizeof ha);
        memset(state[now^1],0,sizeof state[now^1]);
        num[now^1]=0;
        FOR(i,num[now]) {
            decode(state[now][i]);
            
            /*
            cout<<r<<" "<<c<<endl;
            //cout<<f[now][i]<<endl;
            FOR(j,n+1) cout<<a[j]<<" ";
            cout<<endl;
            */
            
            int left=a[c],up=a[c+1];
            ll code;
            
            if (left&&!up) {
                if (c!=n) {
                    memcpy(tmp+1,a+1,(n+1)*sizeof(int));
                    a[c+1]=left,a[c]=0;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                    memcpy(a+1,tmp+1,(n+1)*sizeof(int));
                }
                if (r!=m) {
                    memcpy(tmp+1,a+1,(n+1)*sizeof(int));
                    a[c+1]=0,a[c]=left;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                    memcpy(a+1,tmp+1,(n+1)*sizeof(int));
                }
            }
            if (left&&up) {
                if (a[c]!=a[c+1]) {
                    // (1,2) or (2,1)
                    if (a[c]==1&&a[c+1]==2&&!(r==m&&c==n)) continue;
                    a[c]=a[c+1]=0;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                } else if (a[c]==1) {
                    // a[c]=a[c+1]=1
                    int x=p[c][1],y=p[c+1][1];
                    a[c]=a[c+1]=0;
                    a[y]=1,a[x]=2;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                } else {
                    // a[c]=a[c+1]=2
                    int x=p[c][0],y=p[c+1][0];
                    a[c]=a[c+1]=0;
                    a[y]=1,a[x]=2;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                }           
            }
            if (!left&&!up) {
                if (r!=m&&c!=n) {
                    a[c]=1,a[c+1]=2;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                }
            }
            if (!left&&up) {
                if (r!=m) {
                    memcpy(tmp+1,a+1,(n+1)*sizeof(int));
                    a[c]=up,a[c+1]=0;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                    memcpy(a+1,tmp+1,(n+1)*sizeof(int));
                }
                if (c!=n) {
                    memcpy(tmp+1,a+1,(n+1)*sizeof(int));
                    a[c]=0,a[c+1]=up;
                    code=encode();
                    if (code!=-1) add(now^1,code,f[now][i]);
                    memcpy(a+1,tmp+1,(n+1)*sizeof(int));
                }
            }
        }
        if (r==m&&c==n) {
            FOR(j,num[now^1]) {
                ans=ans+f[now^1][j];
            }
        }
    }
    ans=ans+ans;
    print(ans);
    return 0;
}

貌似是压位DP+高精度...

哪天写写看.....

网上抄的代码，自己翻译，排版了一下，给大家学习。
主要方法是状态压缩dp，然后就是高精度，最后加一点特判。
主要，n或m为1时路径只有1条，而不是0条，
虽然是最短，但没说不可以重复走一个点。
但n=3，m=3这种情况不知道怎么搞，还好好像没这个点……
恩，这是他的题解
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int BIT = 177147+10;
int n,m;
int scan()
{
char cc = ' ';
int re = 0,fh = 1;
while(cc == ' ' || cc == '\r' || cc == '\n')
cc = getchar();
if(cc=='+')
{
cc=getchar();
fh=1;
}
if(cc=='-')
{
cc=getchar();
fh=-1;
}
while('0'<=cc&&cc<='9')
{
re = re * 10 + cc - '0';
cc = getchar();
}
return re * fh;
}

struct state{
int i,d;
state(){}
state(int ii,int dd):i(ii),d(dd)
{
}
};

queue<state>dui;

const int LEN = 10+1;
const int L = 10000;

struct Big{
int d[LEN],len;
Big()
{
memset(d,0,sizeof(d));
len=1;
}

Big operator = (int a)
{
if(!a)
{
*this = Big();
return *this;
}
for(len = 0; a != 0 ; a /= L)
d[++len] = a % L;
}

void print()
{
printf("%d",d[len]);
for(int i=len-1;i;i--)
printf("%04d",d[i]);
}
};
typedef Big BIG;

Big operator + (Big &A,Big &B)
{
Big C;
C.len = max(A.len,B.len) + 1;
for(int i = 1; i <= C.len; ++ i)
{
C.d[i] += A.d[i] + B.d[i];
if(C.d[i] >= L)
{
C.d[i+1] = C.d[i] / L;
C.d[i] %= L;
}
}
while(C.len > 1 && C.d[C.len] == 0)
C.len--;
return C;
}

BIG ans,f[2][BIT];
short v[2][BIT];

int pos(int x,int y)
{
return (y - 1) * m + x - 1;
}

void list(int x,short a[])
{
for(int i=1;i<=m+1;i++)
a[i] = 0;
for(int i = 1; x != 0; ++ i,x = x / 3)
a[i] = x % 3;
}

int zip(short a[],int x,int val1,int val2){
int re=0;
for(int i = m + 1; i != 0 ; -- i)
if(i == x)
re = re * 3 + val1;
else
if(i == x + 1)
re = re * 3 + val2;
else
re = re * 3 + a[i];
return re;
}

short lin[12];

void pipei(int x,short a[],short type)
{
int i,j,p1 = 0,p2 = 0;
if(type==1)
{
for(j=0,i=x+2;i<=m+1;i++)
{
if(a[i]==2)
j++;
if(a[i]==1)
j--;
if(j > 0 && !p1)
{
p1=i;
j--;
}
if(j > 0 && p1)
{
p2=i;
break;
}
}
}
else
{
for(j=0,i=x-1;i;i--)
{
if(a[i]==1)
j++;
if(a[i]==2)
j--;
if(j > 0 && !p2)
{
p2=i;
j--;
}
if(j > 0 && p2)
{

p1=i;
break;
}
}
}
a[p1] = 1;
a[p2] = 2;
}

void update(int i,int zt,BIG &val,short upans = 0)
{
i++;
int i2 = i % 2;
if(!upans)
{
if(v[i2][zt] != i)
{
f[i2][zt] = 0;
v[i2][zt] = i;
dui.push(state(i,zt));
}
f[i2][zt] = f[i2][zt]+val;
}
else
ans = ans + val;
}

short map[21][21];

bool lerror(short a[])
{
int i,j;
for(i=1,j=0;i<=m+1;i++)
{
if(a[i]==1)
j++;
if(a[i]==2)
j--;
if(j<0)
return 1;
}
return j != 0;
}

int main(){
int i,j,end;
m=scan();
n=scan();
end = pos(m,n);
dui.push(state(0,0));
f[0][0] = 1;
v[0][0] = 1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
map[i][j]=1;
while(!dui.empty())
{
state now = dui.front();
dui.pop();
int x,y,tmp;
i = now.i;
BIG & last = f[i%2][now.d];
if(i % m == 0)
now.d *= 3;
x = i % m + 1;
y = i / m + 1;
list(now.d,lin);
if(lin[x] == 1 && lin[x+1] == 2)
{
if(i == end)
update(i,0,last,1);
}else
if(lin[x] == 2 && lin[x+1] == 1)
{
tmp = zip(lin,x,0,0);
update(i,tmp,last);
}
else
if(lin[x] == 0 && lin[x+1] == 0)
{
if(map[x][y+1] && map[x+1][y])
{
tmp = zip(lin,x,1,2);
update(i,tmp,last);
}
}
else
if(lin[x] == 0)
{
if(map[x+1][y])
{
tmp = zip(lin,x,0,lin[x+1]);
update(i,tmp,last);
}
if(map[x][y+1])
{
tmp = zip(lin,x,lin[x+1],0);
update(i,tmp,last);
}
}
else
if(lin[x+1] == 0)
{
if(map[x+1][y])
{
tmp = zip(lin,x,0,lin[x]);
update(i,tmp,last);
}
if(map[x][y+1])
{
tmp = zip(lin,x,lin[x],0);
update(i,tmp,last);
}
}
else
if(lin[x] == lin[x+1])
{
pipei(x,lin,lin[x]);
tmp = zip(lin,x,0,0);
update(i,tmp,last);
}
}
ans = ans + ans;
if(ans.len == 1 && ans.d[1] == 0)
ans = 1;
ans.print();
return 0;
}

1个月后再写- -等我涅磐了

typedef pair int128

名字是---|基于连通性状态压缩的动态规划问题

oRZ lx和lxx的神牛！！！！！！！

（一开始把m和n交换一下，不然状态表示要用long long……）

Formula 1答案*2

使用了连通性状态压缩DP。

但是单单设f会严重爆空间。

可以考虑使用滚动一维的实现方式，设f[0..1,k]。

空间O(2*3^m) 解决了空间问题。

水题

CDQ《连通性状态压缩DP》

看到数据这么小就有一种挂表的冲动........

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

呜呼！n=1或m=1要特判！

状态压缩dp+高精度，速度还是很快的啊！

基于连通性原理的状态压缩动态规划

可以看看noi2008冬令营cdq的论文

这题为何没有人写？？

比较弱，写了个搜索30分。。后面全超，不过也挺欣慰了。。
begin
if (t=n*m)
then if ((x=1)and(y=2))or((x=2)and(y=1))
then begin
s:=s+1;exit;
end
else exit;
for i:=1 to 4 do begin
q:=x+han[i];
p:=y+lie[i];
if (q>0)and(q<=n)and(p>0)and(p<=m)
then if b[q,p]=false then
begin
b[q,p]:=true;
so(q,p,t+1);
b[q,p]:=false;
end;
end;
end;