妈妈我会写插头dp了！！！！！！。。。。
感动啊。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 105 #define maxs 200000 #define mod 20110520 using namespace std; int n,m,map[maxn][maxn],dp[2][2][maxs],tab[maxs][12],table[15]; int s1[maxn],s2[maxn],top=0; int pt[20][3]; char s[maxn]; void ex() { for (int i=1;i<=n;i++) for (int j=i+1;j<=m;j++) swap(map[i][j],map[j][i]); swap(n,m); } void get_table() { table[0]=1; for (int i=1;i<=13;i++) table[i]=table[i-1]*3; for (int i=1;i<177147;i++) { tab[i][0]=tab[i-1][0]+1;int flag=0; if (tab[i][0]==3) {flag=1;tab[i][0]=0;} for (int j=1;j<=10;j++) { tab[i][j]=tab[i-1][j]+flag; if (tab[i][j]==3) {flag=1;tab[i][j]=0;} else flag=0; } } int cnt=0; for (int i=0;i<=2;i++) for (int j=0;j<=2;j++) {cnt++;pt[cnt][1]=i;pt[cnt][2]=j;} } void modify(int x,int bs) { s1[1]=bs;s2[1]=pt[x][1];s1[2]=bs+1;s2[2]=pt[x][2]; top=2; } int find(int x) { int a[15],data=0; for (int i=0;i<=11;i++) a[i]=tab[x][i]; for (int i=1;i<=top;i++) a[s1[i]]=s2[i]; for (int i=11;i>=0;i--) data=data*3+a[i]; return data; } void plug_dp() { dp[0][m&1][0]=1; for (int i=1;i<=n;i++) { memset(dp[i&1],0,sizeof(dp[i&1])); for (int j=0;j<table[m];j++) dp[i&1][0][j*3]=dp[(i&1)^1][m&1][j]; for (int j=1;j<=m;j++) { for (int k=0;k<table[m+1];k++) dp[i&1][j&1][k]=0; for (int k=0;k<table[m+1];k++) { if (map[i][j]) { if ((tab[k][j-1]==0) && (tab[k][j]==0)) { modify(3,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(5,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(7,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; } else if ((tab[k][j-1]==0) && (tab[k][j]==1)) { modify(1,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(4,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; } else if ((tab[k][j-1]==0) && (tab[k][j]==2)) { modify(2,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(7,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; } else if ((tab[k][j-1]==1) && (tab[k][j]==0)) { modify(1,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(2,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; } else if ((tab[k][j-1]==1) && (tab[k][j]==1)) { //nothing here. } else if ((tab[k][j-1]==1) && (tab[k][j]==2)) { //nothing here. } else if ((tab[k][j-1]==2) && (tab[k][j]==0)) { modify(3,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; modify(4,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod; } else if ((tab[k][j-1]==2) && (tab[k][j]==1)) { //nothing here. } else {modify(1,j-1);dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][find(k)])%mod;} } else if ((tab[k][j-1]==0) && (tab[k][j]==0)) dp[i&1][j&1][k]=(dp[i&1][j&1][k]+dp[i&1][(j&1)^1][k])%mod; } } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=m;j++) { if (s[j-1]=='_') map[i][j]=1; else map[i][j]=0; } } if (n<m) ex(); get_table(); plug_dp(); printf("%d ",dp[n&1][m&1][0]); return 0; }