NOI2010 旅行路线

题目:

  2010年,世博会在中国上海举办,吸引了数以千万计的中外游客前来参观。暑假期间小Z也来到了上海世博园,她对世博园的拥挤早有所闻,对有的展馆甚至要 排上好几个小时的队才能进入也做好了充分准备,但为了使得自己的世博之旅更加顺利舒畅,小Z决定在游玩之前先制定一份详细的旅行路线。
  小Z搜集到了世博园的地图,她发现从整体上看世博园是一块非常狭长的区域,而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个n × m的矩阵(n≤3),其中每一个格子为一个主题展馆。
  由于不同展馆受到的关注度会有一些差别,因此排队时间的长短也不尽相同。小Z根据统计信息给每一个展馆(x, y)标记了Tx,y = 0或1,如果Tx,y = 1,表示这个展馆非常热门,需要排很长时间的队;如果Tx,y = 0,表示这个展馆相对比较普通,几乎不需要排队即可进入参观。小Z希望能够制定一份合理的路线,使得能交替参观热门馆和普通馆,既不会因为总是参观热门馆而长时间在排队,也不会因为总是参观普通馆而使得游览过于平淡。同时,小Z办事很讲究效率,她希望在游遍所有展馆的同时,又不会走冤枉路浪费体力。因此她 希望旅行路线满足以下几个限制:
  在参观完位于(x, y)的展馆后,下一个参观的是一个相邻的且未被参观过的展馆(x', y'),即 |x-x'|+|y-y'|=1;
  路线的起点位于整个矩阵的边界上,即x = 1或x = n或y = 1或y = m;
  她制定了一个长度为n*m的 01 序列L,她希望第i个参观的展馆(x,y)满足Tx,y=Li。
  小Z想知道有多少条不同的旅行路线能够满足她的要求。由于最终的结果可能很大,小Z只想知道可行的旅行路线总数mod 11192869的值。
  

思路:

  题目要求找一条走遍所有点又不重复的路径,再加上 ,不难想到插头dp。
  为了下文描述方便,设每个点的 值表示这个点在最后的路线中是第 个走到的。
  为了在插头dp的过程中能知道 ,肯定是要记录到达它的点的 值,那么就可以直接 记录当前轮廓线以上的 个点的 值。但只有这样还是不能确定当前点是 还是 ,所以插头也要分成递增和递减两类,这样就要再用 记录插头状态,所以总的状态数就是 (但事实上根本达不到)。
  ps:感觉别人好像用了一些方法压掉了一些状态,跑到明显比我快很多qwq。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 11192869, N = 55, P = 1e6 + 3;
struct HashTable {
    ll rel[P];
    int key[P], vec[P], sz;
    void clear() {
        rep(i, 1, sz) rel[vec[i]] = -1;
        sz = 0;
    }
    void init() {mset(rel, -1);}
    int& operator[] (ll val) {
        int pos = val % P;
        while(rel[pos] != -1 && rel[pos] != val) pos = (pos + 1) % P;
        if(rel[pos] == -1) {rel[pos] = val; key[pos] = 0; vec[++sz] = pos;}
        return key[pos];
    }
} dp[2];

int plg[5], num[5];
ll encode() {
    ll code = 0;
    rep(i, 1, 3) code = code << 8 | num[i];
    rep(i, 0, 3) code = code << 2 | plg[i];
    return code;
}
void decode(ll code) {
    drep(i, 3, 0) plg[i] = code & 3, code >>= 2;
    drep(i, 3, 1) num[i] = code & 255, code >>= 8;
}

char getAChar() {
    char c;
    do c = getchar(); while(c == ' ' || c == '\n' || c == '\r');
    return c;
}
int mp[55][5], ned[155];
int n, m;
bool check(int i, int j) {
    return i == 1 || i == m || j == 1 || j == n;
}

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    File(trip);
    scanf("%d%d", &n, &m);
    rep(i, 1, n) rep(j, 1, m) mp[j][n - i + 1] = getAChar();
    rep(i, 1, n * m) ned[i] = getAChar();
    if(n == 1 && m == n) return printf("%d\n", ned[1] == mp[1][1]), 0;
    dp[0].init(); dp[1].init();
    int o = 1, d = 0;
    dp[o].clear(); dp[o][0] = 1;
    rep(i, 1, m) {
        rep(j, 1, n) {
            std::swap(o, d);
            dp[o].clear();
            rep(_x, 1, dp[d].sz) {
                int x = dp[d].vec[_x], val = dp[d].key[x];
                ll bin = dp[d].rel[x];
                decode(bin);
                int b1 = plg[j - 1], b2 = plg[j];
                if(b1 == 0 && b2 == 0) {
                    rep(x, 1, n * m) {
                        if(ned[x] != mp[i][j]) continue;
                        num[j] = x;
                        plg[j - 1] = 1; plg[j] = 2;
                        (dp[o][encode()] += val) %= MOD;
                        plg[j - 1] = 2; plg[j] = 1;
                        (dp[o][encode()] += val) %= MOD;
                        if(check(i, j) && x == 1) {
                            plg[j - 1] = 1; plg[j] = 0;
                            (dp[o][encode()] += val) %= MOD;
                            plg[j - 1] = 0; plg[j] = 1;
                            (dp[o][encode()] += val) %= MOD;
                        }
                        if(x == n * m) {
                            plg[j - 1] = 2; plg[j] = 0;
                            (dp[o][encode()] += val) %= MOD;
                            plg[j - 1] = 0; plg[j] = 2;
                            (dp[o][encode()] += val) %= MOD;
                        }
                    }
                }
                else if(b1 != 0 && b2 == 0) {
                    if(b1 == 1) num[j] = num[j - 1] + 1;
                    else num[j] = num[j - 1] - 1;
                    if(num[j] < 1 || num[j] > n * m) continue;
                    if(ned[num[j]] != mp[i][j]) continue;
                    plg[j - 1] = b1; plg[j] = 0;
                    (dp[o][encode()] += val) %= MOD;
                    plg[j - 1] = 0; plg[j] = b1;
                    (dp[o][encode()] += val) %= MOD;
                    if((check(i, j) && num[j] == 1) || num[j] == n * m) {
                        plg[j - 1] = plg[j] = 0;
                        (dp[o][encode()] += val) %= MOD;
                    }
                }
                else if(b1 == 0 && b2 != 0) {
                    if(b2 == 1) num[j] = num[j] + 1;
                    else num[j] = num[j] - 1;
                    if(num[j] < 1 || num[j] > n * m) continue;
                    if(ned[num[j]] != mp[i][j]) continue;
                    plg[j - 1] = b2; plg[j] = 0;
                    (dp[o][encode()] += val) %= MOD;
                    plg[j - 1] = 0; plg[j] = b2;
                    (dp[o][encode()] += val) %= MOD;
                    if((check(i, j) && num[j] == 1) || num[j] == n * m) {
                        plg[j - 1] = plg[j] = 0;
                        (dp[o][encode()] += val) %= MOD;
                    }
                }
                else if(b1 == 1 && b2 == 2) {
                    if(num[j - 1] == num[j] - 2) {
                        plg[j - 1] = plg[j] = 0;
                        num[j] = num[j - 1] + 1;
                        if(ned[num[j]] != mp[i][j]) continue;
                        (dp[o][encode()] += val) %= MOD;
                    }
                }
                else if(b1 == 2 && b2 == 1) {
                    if(num[j - 1] == num[j] + 2) {
                        plg[j - 1] = plg[j] = 0;
                        num[j] = num[j - 1] - 1;
                        if(ned[num[j]] != mp[i][j]) continue;
                        (dp[o][encode()] += val) %= MOD;
                    }
                }
            }
        }
        std::swap(o, d);
        dp[o].clear();
        rep(_x, 1, dp[d].sz) {
            int x = dp[d].vec[_x], val = dp[d].key[x];
            ll bin = dp[d].rel[x];
            decode(bin);
            if(plg[n] != 0) continue;
            drep(i, n, 1) plg[i] = plg[i - 1];
            plg[0] = 0;
            (dp[o][encode()] += val) %= MOD;
        }
    }
    int ans = 0;
    rep(_x, 1, dp[o].sz) {
        int x = dp[o].vec[_x], val = dp[o].key[x];
        ll bin = dp[o].rel[x];
        decode(bin);
        bool flag = true;
        rep(i, 0, n) flag &= (plg[i] == 0);
        if(flag) (ans += val) %= MOD;
    }
    printf("%d\n", ans);
    return 0;
}