高端网站制作公司,网站建设项目的结论,哈尔滨网站排名公司,免费凡科网站description BZOJ 定义两个结点数相同的图\(G1\)与图\(G2\)的异或为一个新的图\(G\), 其中如果\((u,v)\)在\(G1\)与\(G2\)中的出现次数之和为\(1\), 那么边\((u,v)\)在\(G\)中, 否则这条边不在\(G\)中. 现在给定\(s\)个结点数相同的图\(G1...s\),设\(S{G1,G2,...,Gs},\) 问\(S\…description BZOJ 定义两个结点数相同的图\(G1\)与图\(G2\)的异或为一个新的图\(G\), 其中如果\((u,v)\)在\(G1\)与\(G2\)中的出现次数之和为\(1\), 那么边\((u,v)\)在\(G\)中, 否则这条边不在\(G\)中. 现在给定\(s\)个结点数相同的图\(G1...s\),设\(S{G1,G2,...,Gs},\) 问\(S\)有多少个子集的异或为一个连通图.\(n\le 10,s\le 60\) solution 考虑如何减掉图不连通的方案,此时图被分割成的连通块数一定大于一个。 先求出连通块数至少为\(k\)的方案数,那么枚举子集划分,\(O(B_n),B_{10}21147\); 之后需要保证集合之间无连边,即\(s\)个图的异或不能和集合间对应边的集合\(S\)有交。 求集合与\(S\)的交集插入线性基,设线性基内的元素个数为\(c\),那么最后答案为\(2^{s-c}\)。 这样我们得到了\(f(x)\)表示连通块个数\(\ge x\)的方案数。 设\(g(x)\)表示连通块个数\(x\)的方案数,那么要求的是\(g(1)\)。 针对子集划分,我们有斯特林数。\[f(k)\sum_{mk}^{n}\begin{Bmatrix}m\\k\end{Bmatrix}g(m)\] 考虑每个连通块个数\(m\)的方案,因为当前假定有\(k\)个可能连通块, 那么这\(m\)个连通块会被划分为\(k\)个无序集合,因此重复计算了\(\begin{Bmatrix}m\\k\end{Bmatrix}\)次。 斯特林反演即可。\[g(k)\sum_{mk}^{n}(-1)^{m-k}\begin{bmatrix}m\\k\end{bmatrix}f(m)\] \[g(1)\sum_{m1}^{n}(-1)^{m-1}(m-1)!f(m)\] code #includebits/stdc.h
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FL a
using namespace std;
typedef long long ll;
const int N1e510;
const int mod998244353;
inline ll read(){ll data0,w1;char chgetchar();while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch9ch0)datadata*10ch-48,chgetchar();return data*w;
}
inline void file(){freopen(FL.in,r,stdin);freopen(FL.out,w,stdout);
}int s,n,G[60][10][10],get[45],in[10];ll p[45],fac[11],ans;
void dfs(int x,int t){int i;if(xn){int cnt0,tot,g,j;ll tmp;memset(p,0,sizeof(p));memset(get,0,sizeof(get));for(g0;gs;g){tmptot0;for(i0;in;i)for(ji1;jn;j)if(in[i]^in[j])tmp|1ll*G[g][i][j]tot,tot;for(i0;itot;i)if(tmp1lli){if(p[i])tmp^p[i];else{p[i]tmp;cnt;break;}}}ans(t1?1:-1)*fac[t-1]*(1lls-cnt);return;}for(i1;it1;i)in[x]i,dfs(x1,max(i,t));
}mapint,intM;
int main()
{sread();int i,j,g,pp;string c;for(ifac[0]1;i10;i)fac[i]1ll*fac[i-1]*i;for(i2;i10;i)M[i*(i-1)/2]i;for(g0,pp;gs;g){cinc;nM[c.length()];pp0;for(i0;in;i)for(ji1;jn;j)G[g][i][j]c[pp]-48;}dfs(0,0);printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/cjfdf/p/10325751.html
