大家好，又见面了，我是你们的朋友全栈君。
传送门
直接求连通的不好做，考虑容斥
设 \(g_i\) 表示至少有 \(i\) 个连通块的方案数，\(f_i\) 表示恰好有 \(i\) 个的
那么
\[g_x=\sum_{i=x}^{n}\begin{Bmatrix}x \\ i\end{Bmatrix}f_i\iff f_x=\sum_{i=x}^{n}(-1)^{i-x}\begin{bmatrix}x \\ i\end{bmatrix}g_i\]
那么
\[f_1=\sum_{i=1}^{n}(-1)^{i-1}(i-1)!g_i\]
求 \(g\)
考虑枚举点的拆分，相当于是不同的集合之没有边，这部分直接用线性基求出方案
# include <bits/stdc++.h> using namespace std; typedef long long ll; int n = 1, graph[65][15][15], m, id[15]; char ch[2333]; ll fac[15], ans, bc[65], v; void Dfs(int x, int f) { register int i, j, k, tot, num; if (x > n) { memset(bc, 0, sizeof(bc)), num = 0; for (i = 1; i <= m; ++i) { for (v = tot = 0, j = 1; j <= n; ++j) for (k = j + 1; k <= n; ++k) if (id[j] != id[k]) v |= (ll)graph[i][j][k] << tot, ++tot; for (j = 0; j < tot; ++j) if (v >> j & 1) { if (!bc[j]) { bc[j] = v, ++num; break; } v ^= bc[j]; } } ans += (ll)((f & 1) ? 1 : -1) * fac[f - 1] * (1ll << (m - num)); return; } for (i = 1; i <= f + 1; ++i) id[x] = i, Dfs(x + 1, max(i, f)); } int main() { register int i, j, k, len, cnt; for (scanf("%d", &m), i = 1; i <= m; ++i) { scanf(" %s", ch + 1), len = strlen(ch + 1); while (n * (n - 1) / 2 < len) ++n; for (cnt = 0, j = 1; j <= n; ++j) for (k = j + 1; k <= n; ++k) graph[i][j][k] = ch[++cnt] - '0'; } for (fac[0] = 1, i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i; Dfs(1, 0), printf("%lld\n", ans); return 0; }转载于:https://www.cnblogs.com/cjoieryl/p/10182369.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107117.html原文链接：https://javaforall.net
