bzoj 2331: [SCOI2011]地板

.

题意：用L形地砖铺满有障碍的n×m的地板，问方案数。
题解：插头DP
0表示没插头，1表示这个插头连出去的还没拐弯，2表示这个插头连出去拐过弯了。
转移：
00 => 01 10 22
11 => 00
10 => 01 20
01 => 10 02
20 => 02 00
02 => 20 00
代码：

#include<bits/stdc++.h>
using namespace std;

int n, m;
const int hmod = 402503, mod = 20110520;
char mp[110][110], tmp[110][110];
struct ha
{
    struct node
    {
        int hh, ori, val;
        node *n;
        node(int hh = 0, int ori = 0, node *n = NULL):hh(hh), ori(ori), val(0), n(n){}
    } *fst[hmod], pool[200000], *now;
    void clear()
    {
        memset(fst, 0, sizeof(fst));
        now = pool;
    }
    ha()
    {
        clear();
    }
    node *ins(int x, int hh)
    {
        node *p = new(now++) node(hh, x, fst[hh]);
        return fst[hh] = p;
    }
    int &operator[](int x)
    {
        int hh = x % hmod;
        for (node *it = fst[hh]; it; it = it->n)
            if (it->ori == x)
                return it->val;
        return ins(x, hh)->val;
    }
}f[2];

int get(int x, int y)
{
    return x >> (y << 1) & 3;
}
void chg(int &x, int y, int z)
{
    x = ((x >> (y + 1 << 1) << 2) + z << (y << 1)) + (x & (1 << (y << 1)) - 1);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);
    if (n < m)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                tmp[j][i] = mp[i][j];
        memcpy(mp, tmp, sizeof(mp));
        swap(n, m);
    }
    int p = 0;
    f[p].clear();
    f[p][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p ^= 1;
        f[p].clear();
        for (ha::node *it = f[p^1].pool; it != f[p^1].now; it++)
            (f[p][it->ori << 2] += it->val) %= mod;
        for (int j = 1; j <= m; j++)
        {
            p ^= 1;
            f[p].clear();
            for (ha::node *it = f[p^1].pool; it != f[p^1].now; it++)
            {
                if (mp[i][j] == '*')
                    (f[p][it->ori] += it->val) %= mod;
                else
                {
                    int l = get(it->ori, j), u = get(it->ori, j + 1);
                    if (l == 0 && u == 0)
                    {
                        if (mp[i+1][j] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 1);
                            (f[p][hh] += it->val) %= mod;
                        }
                        if (mp[i][j+1] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j+1, 1);
                            (f[p][hh] += it->val) %= mod;
                        }
                        if (mp[i][j+1] == '_' && mp[i+1][j] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 2);
                            chg(hh, j+1, 2);
                            (f[p][hh] += it->val) %= mod;
                        }
                    }
                    else if (l == 1 && u == 1)
                    {
                        int hh = it->ori;
                        chg(hh, j, 0);
                        chg(hh, j+1, 0);
                        (f[p][hh] += it->val) %= mod;
                    }
                    else if (l == 1 && u == 0)
                    {
                        if (mp[i][j+1] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 0);
                            chg(hh, j+1, 1);
                            (f[p][hh] += it->val) %= mod;
                        }
                        if (mp[i+1][j] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 2);
                            (f[p][hh] += it->val) %= mod;
                        }
                    }
                    else if (l == 0 && u == 1)
                    {
                        if (mp[i][j+1] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j+1, 2);
                            (f[p][hh] += it->val) %= mod;
                        }
                        if (mp[i+1][j] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 1);
                            chg(hh, j+1, 0);
                            (f[p][hh] += it->val) %= mod;
                        }
                    }
                    else if (l == 2 && u == 0)
                    {
                        if (mp[i][j+1] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 0);
                            chg(hh, j+1, 2);
                            (f[p][hh] += it->val) %= mod;
                        }
                        int hh = it->ori;
                        chg(hh, j, 0);
                        chg(hh, j+1, 0);
                        (f[p][hh] += it->val) %= mod;
                    }
                    else if (l == 0 && u == 2)
                    {
                        if (mp[i+1][j] == '_')
                        {
                            int hh = it->ori;
                            chg(hh, j, 2);
                            chg(hh, j+1, 0);
                            (f[p][hh] += it->val) %= mod;
                        }
                        int hh = it->ori;
                        chg(hh, j, 0);
                        chg(hh, j+1, 0);
                        (f[p][hh] += it->val) %= mod;
                    }
                }
            }/*
            printf("i:%d j:%d\n", i, j);
            for (ha::node *it = f[p].pool; it != f[p].now; it++)
            {
                printf("S: ");
                for (int j = 1; j <= m+1; j++)
                    printf("%d ", get(it->ori, j));
                printf("val: %d\n", it->val);
            }*/
        }
    }
    printf("%d\n", f[p][0]);
}