感觉有点厉害的套路。
题意：给出一个网格图，有些边缺失，问给边定向出来无环的方案数。\(n,m\le 6\)。
做法：
考虑一个叫色多项式的东西，我们定义集合幂级数 \(F\)，\([x ^S]\) 为 \(1\) 当且仅当 \(S\) 这个点集是独立集。那么我们考虑对这个图进行 \(c\) 染色，要求相邻的点不能染同色，那么显然这样的方案为 \(\sum [x^U]F^i\binom{c}{i}\)，乘法是子集卷积。一个结论是，一个图的无环定向等于其 \(-1\) 染色的结果，把柿子稍微整理一下，就是 \(\sum[x^U]F^i(-1)^i\)，我们再考虑无环定向在干什么，就是在枚举一个剥开 \(0\) 度点的划分，写出来的柿子只和这个差 \((-1)^n\)。
所以我们就可以把问题转化为 \(-1\) 染色即可，\(-1\) 染色比较难理解，就可以认为是 \(mod-1\) 染色，直接压一下颜色的等价类，轮廓线 dp 一下，就可以做到贝尔数乘上 \(\operatorname{poly}(nm)\) 的复杂度。
代码有些细节，感觉是我太久没写代码了有点呆滞了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 16, mod = 0;
int n, m, h[maxn][maxn], sh[maxn][maxn];
string read() {char c = getchar();string s;while(c != ' ' && c != '|' && c != '-' && c != '+')c = getchar();while(!(c != ' ' && c != '|' && c != '-' && c != '+'))s += c, c = getchar();return s;
}
struct node {int a[maxn];int& operator[](int x) {return a[x];}friend bool operator<(node x, node y) {for (int i = 1; i <= m; i++)if(x[i] != y[i])return x[i] < y[i];return 0;}int get_max() {int ans = 0;for (int i = 1; i < maxn; i++)ans = max(ans, a[i]);return ans;}
} ;
int vis[maxn];
node renew(node x) {int t = x.get_max();for (int i = 1; i <= t; i++)vis[i] = 0;int cnt = 0;for (int i = 1; i < maxn; i++) {if(!x[i])continue;if(!vis[x[i]])vis[x[i]] = ++cnt;x[i] = vis[x[i]];}return x;
}
map<node, int> mp;
node tp[10005], nw;
int dp[maxn][maxn][10005], tot;
void dfs(int d, int lim) {if(d > m) {// if(n > 2 && tot % 10 == 0)// cout << d << "Adsaf" << tot << endl;tp[++tot] = nw;mp[nw] = tot;//cout << tot << endl;return ;}for (int i = 1; i <= lim + 1; i++)nw[d] = i, dfs(d + 1, max(i, lim)), nw[d] = 0;
}
int coef[maxn];
char s[maxn * 10];
void solve() {tot = 0;memset(dp, 0, sizeof(dp));mp.clear();cin >> n >> m; cin.getline(s, 2 * m);
// cout << n << " " << m << endl;for (int i = 1; i <= n; i++) {//s = read();for (int j = 0; j < 2 * m; j++)s[j] = ' ';cin.getline(s, 2 * m);for (int j = 0, p = 1; j < 2 * m, p < m; p++, j += 2) {if(s[j + 1] == '-')h[i][p] = 1;elseh[i][p] = 0;}// cout << s << endl;if(i != n) {for (int j = 0; j < 2 * m; j++)s[j] = ' ';cin.getline(s, 2 * m);for (int j = 0, p = 1; j <= 2 * m, p <= m; p++, j += 2) {if(s[j] == '|')sh[i][p] = 1;elsesh[i][p] = 0;}}// cout << i << " " << s << endl;}coef[0] = 1;for (int i = 1; i <= m; i++)coef[i] = coef[i - 1] * (mod - i);
// if(n <= 2)dfs(1, 0);memset(dp, 0, sizeof(dp));for (int i = 1; i <= tot; i++) {dp[1][m][i] = coef[tp[i].get_max()];for (int j = 1; j < m; j++) {if(h[1][j] && tp[i][j] == tp[i][j + 1])dp[1][m][i] = 0;}// cout << dp[1][m][i] << " " << i << endl;}//cout << tot << endl;int x = 1, y = m;
// cout << sh[1][5] << endl;for (int i = 2; i <= n; i++) {for (int j = 1; j <= m; j++) {for (int k = 1; k <= tot; k++) {int t = tp[k].get_max();for (int l = 1; l <= t + 1; l++) {node tmp = tp[k];tmp[j] = l; int coef = 1;if(sh[i - 1][j] && tmp[j] == tp[k][j])continue;if(j > 1 && h[i][j - 1] && tmp[j] == tmp[j - 1])continue;tmp = renew(tmp);if(coef)coef = (l == t + 1 ? mod - l : 1);// cout << i << " " << j << " " << mp[tmp] << " " << k << " " << coef << endl;dp[i][j][mp[tmp]] = (dp[i][j][mp[tmp]] + dp[x][y][k] * coef);}}x = i, y = j;
// int ans = 0;
// for (int i = 1; i <= tot; i++)
// ans += dp[x][y][i];
// cout << ans << endl;
// cout << ans << endl;
// for (int k = 1; k <= tot; k++)
// cout << dp[i][j][k] << " ";
// cout << endl;}}int ans = 0;for (int i = 1; i <= tot; i++)ans = (ans + dp[n][m][i]);cout << ans * ((n * m) % 2 ? -1 : 1) << endl;
}
signed main() {int T; cin >> T;while(T--)solve();return 0;
}
/*
4
2 2
+-++ +
2 2
+-+
|
+ +
2 2
+-+
|
+-+
2 2
+-+
| |
+-+
*/