Bipartite Bicolored Graphs
发布时间:2020-12-14 04:34:56 所属栏目:大数据 来源:网络整理
导读:? 由i个点和j个点组成的二分图个数为 $3_{ij}$,减去不联通的部分得到得到由i,j个点组成的联通二分图个数 ?$g_{i,j} = 3_{ij} - sum_{k=1}^i sum_{l=0}^j g_{k,l} C_{i-1,k-1} C_{j,l} 3_{(i-k)(j-l)}$ 然后再dp一遍 #include bits/stdc++.h using namesp
? 由i个点和j个点组成的二分图个数为 $3_{ij}$,减去不联通的部分得到得到由i,j个点组成的联通二分图个数 ?$g_{i,j} = 3_{ij} - sum_{k=1}^i sum_{l=0}^j g_{k,l} C_{i-1,k-1} C_{j,l} 3_{(i-k)(j-l)}$ 然后再dp一遍 #include <bits/stdc++.h> using namespace std; #define rep(i,j,k) for (int i = int(j); i <= int(k); ++ i) #define dwn(i,k) for (int i = int(j); i >= int(k); -- i) typedef long long LL; const LL MOD = 175781251; const int N = 107; LL fac[N],inv[N],pw[N * N],g[N][N],f[N]; inline LL comb(LL n,LL m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; } int main() { fac[0] = 1; rep(i,1,N - 1) fac[i] = fac[i - 1] * i % MOD; inv[0] = inv[1] = 1; rep(i,2,N - 1) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD; rep(i,N - 1) (inv[i] *= inv[i - 1]) %= MOD; pw[0] = 1; rep(i,1,N * N - 1) pw[i] = pw[i - 1] * 3 % MOD; rep(i,100) rep(j,0,100 - i) { g[i][j] = pw[i * j]; // A集合中i 个点标号 1 -i, B集合中j个点标号1-j // 枚举A集合中第一个点所在联通二分图 rep(k,i) rep(l,0,j) { if (k == i && l == j) continue; g[i][j] += MOD - g[k][l] * comb(i - 1,k - 1) % MOD * comb(j,l) % MOD * pw[(i - k) * (j - l)] % MOD; g[i][j] %= MOD; } } f[0] = 1; rep(i,100) rep(j,0,i - 1) rep(k,i - 1 - j) { f[i] += g[j + 1][k] * comb(i - 1,j) % MOD * comb(i - 1 - j,k) % MOD * f[i - 1 - j - k] % MOD; f[i] %= MOD; } int n; while (scanf("%d",&n),n) { cout << f[n] << ‘n‘; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |