NOI
，世博会在中国上海举办，吸引了数以千万计的中外游客前来参观。暑假期间小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的值。
输入：
第一行包含两个正整数n, m。
第2行至第n+ 1行，每行有m个01整数，其中第i+ 1行第j个数表示Ti,j。
第n+ 2行有n*m个01整数，其中第i个数表示Li的值。
输出：
仅包含一个整数，表示可行的旅行路线总数mod 11192869的值。
解析：
#include <bits/stdc++.h>using namespace std;const int maxn = 5, maxm = 55, maxl = 155, mod = 11192869, mo = 500000;typedef long long ll;typedef unsigned int uint;int a[maxn][maxm], L[maxl];int n, m, pos[maxn], plug[maxn], head[2][500010], tot[2], cur, pre, chc[maxl], ans;struct State{bitset<maxl> used;uint stt;int val, nxt;State() { val = nxt = stt = 0; used.reset(); }}ptr[2][1001000];void hah(uint stt, int val, bitset<maxl> &used) {int x = stt % mo;for(int i = head[cur][x]; i; i = ptr[cur][i].nxt) if(ptr[cur][i].stt == stt) {ptr[cur][i].val = (ptr[cur][i].val + val) % mod; return;}ptr[cur][++tot[cur]].stt = stt;ptr[cur][tot[cur]].val = val;ptr[cur][tot[cur]].used = used;ptr[cur][tot[cur]].nxt = head[cur][x];head[cur][x] = tot[cur];}uint encode() {uint stt = 0;for(int i = 1; i <= n; i++) stt = (stt << 8) + pos[i];for(int i = 0; i <= n; i++) stt = (stt << 2) + plug[i];return stt;}void decode(uint stt) {for(int i = n; i >= 0; i--) plug[i] = stt & 3, stt >>= 2;for(int i = n; i; i--) pos[i] = stt & 255, stt >>= 8; }void solve() {bitset<maxl> used;used.reset();cur = 0; pre = 1; hah(0, 1, used);for(int j = 1; j <= m; j++) {// 新的一行要把plug整体右移for(int t = 1; t <= tot[cur]; t++) {decode(ptr[cur][t].stt);for(int i = n - 1; i >= 0; i--) plug[i + 1] = plug[i]; plug[0] = 0;ptr[cur][t].stt = encode();}for(int i = 1; i <= n; i++) {swap(cur, pre); tot[cur] = 0;memset(head[cur], 0, sizeof(head[cur]));for(int t = 1; t <= tot[pre]; t++) {uint stt = ptr[pre][t].stt; int val = ptr[pre][t].val;used = ptr[pre][t].used;decode(stt);int r = plug[i - 1], d = plug[i];int cnt = 0;if(!r && !d) for(int i = 1; i <= n * m; i++) chc[++cnt] = i;else {if(r == 1) chc[++cnt] = pos[i-1] - 1;else if(r == 2) chc[++cnt] = pos[i-1] + 1;if(d == 1) chc[++cnt] = pos[i] - 1;else if(d == 2) chc[++cnt] = pos[i] + 1;}// 当前位置可能会填哪些数sort(chc + 1, chc + 1 + cnt);cnt = unique(chc + 1, chc + 1 + cnt) - chc - 1;for(int hh = 1; hh <= cnt; hh++) {int x = chc[hh]; // 枚举当前位置填的数，判断是否合法if(a[i][j] != L[x]) continue; if(used[x]) continue;if(r == 1 && x != pos[i - 1] - 1) continue;if(r == 2 && x != pos[i - 1] + 1) continue;if(d == 1 && x != pos[i] - 1) continue;if(d == 2 && x != pos[i] + 1) continue;if(x == 1 && i > 1 && i < n && j > 1 && j < m) continue;if(i == n && j == m) ans = (ans + val) % mod;used[x] = 1; int od = pos[i]; pos[i] = x;// cout << x << endl;for(int npr = 0; npr <= 2; npr++) for(int npd = 0; npd <= 2; npd++) {// 枚举新的插头，判断是否合法，这部分我写的比较冗杂，或许可以精简一下int pnum = (r > 0) + (d > 0) + (npr > 0) + (npd > 0);if(x != 1 && x != n * m && pnum != 2) continue;if((x == 1 || x == n * m) && pnum != 1) continue;if(npr == npd && npr) continue;if(j == m && npr) continue; if(i == n && npd) continue;if((npr == 1 || npd == 1) && used[x - 1]) continue;if((npr == 2 || npd == 2) && used[x + 1]) continue;if(npr == 1 && a[i][j+1] != L[x - 1]) continue;if(npr == 2 && a[i][j+1] != L[x + 1]) continue;if(npd == 1 && a[i+1][j] != L[x - 1]) continue;if(npd == 2 && a[i+1][j] != L[x + 1]) continue;// 当前转移合法，更新下一位置的状态和dp值plug[i - 1] = npr; plug[i] = npd;hah(encode(), val, used);plug[i - 1] = r; plug[i] = d;}used[x] = 0; pos[i] = od;}}}}}int main() {// printf("%lf\n", (double)(&b2-&b1)/1024/1024);// freopen("trip.in", "r", stdin);// freopen("trip.out", "w", stdout);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &a[i][j]);for(int i = 1; i <= n * m; i++) scanf("%d", &L[i]);L[0] = L[n * m + 1] = 521;for(int i = 0; i <= m + 1; i++) a[0][i] = a[n + 1][i] = 233;for(int i = 1; i <= n; i++) a[i][0] = a[i][m + 1] = 233;solve();printf("%d\n", ans);return 0;}
NOI 世博会在中国上海举办 吸引了数以千万计的中外游客前来参观。暑假期间小Z也来到了上海世博园 她对世博园的拥挤早有所闻 对有的展馆甚至要排上好几个小时的队才能进入也做好了充分
