真是菜到爆炸。。。。容斥写反(反正第一次写qwq)


题意:$n-1$个公司,每个公司可以连一些边,求每个边让不同公司连的生成树方案数。

矩阵树定理+容斥原理(注意到$n$不是很大)

枚举公司参与与否的状态,每次重构矩阵,把参与连边的公司可以连的边写在矩阵中,然后求出方案。

代码中的$Gauss()$是辗转相除求解,$Gauss2()$是通过求逆元求解(貌似我的辗转相除更快(雾))

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
#define R register ll
char B[<<],*S=B,*T=B;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
const int M=;
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,ans=,C; ll a[][]; vector<pair<int,int> > q[];
#define pb push_back
inline int Gauss() { ll ans=;
for(R i=;i<n;++i) {
for(R j=i+;j<n;++j) while(a[j][i]) {
ll t=a[i][i]/a[j][i];
for(R k=i;k<n;++k) (a[i][k]-=t*a[j][k])%=M;
swap(a[i],a[j]); ans=-ans;
} ans=(ans*a[i][i])%M; if(!ans) return ;
} return (ans+M)%M;
}
inline ll Inv(int x) {
if(x==) return ; if(x<) return ;
return (M-M/x*Inv(M%x))%M;
}
inline int Gauss2() { register ll ans=;
for(R i=;i<n;++i) for(R j=i+;j<n;++j) {
if(!a[i][i]) return ; if(!a[j][i]) continue;
register ll t=(ll)a[j][i]*Inv(a[i][i]%M)%M;
for(R k=i;k<n;++k) a[j][k]=((a[j][k]-t*a[i][k])%M+M)%M;
} for(R i=;i<n;++i) ans=ans*a[i][i]%M; return ans;
}
signed main() {
n=g(); for(R i=,x;i<n;++i) { x=g();
for(R j=,u,v;j<=x;++j) u=g(),v=g(),q[i].pb(make_pair(u,v));
} C=<<(n-);
for(R i=;i<C;++i) { R cnt=; memset(a,,sizeof(a));
for(R j=;j<n;++j) if(i&(<<j-)) {
for(R k=,u,v;k<q[j].size();++k)
u=q[j][k].first,v=q[j][k].second,
++a[u][u],++a[v][v],--a[u][v],--a[v][u];
++cnt;
} if((n-cnt)&) ans=(ans+Gauss2())%M;
else ans=(ans-Gauss2()+M)%M;
} printf("%lld\n",ans);
}

2019.06.02

最新文章

  1. jsp的三种自定义标签 写法示例
  2. 【HTML5】audio音频
  3. 如何拷贝CMD命令行文本到粘贴板
  4. Java 图片提取RGB数组 RGBOfCharMaps (整理)
  5. 用java开发的网站或者程序
  6. Struts2 DMI的使用
  7. 使用F#开发量化模型都缺什么?
  8. css布局理解
  9. laravel使用多个数据库连接
  10. cocos2d Android.mk自动添加类
  11. 迷宫问题 (bfs广度优先搜索记录路径)
  12. Spring Cloud Zuul 中文文件上传乱码
  13. ArrayList与List性能测试
  14. &lt;yii 框架学习&gt; yii 框架改为中文提示
  15. [javascript] Promise简单学习使用
  16. 科学计算三维可视化---Traits属性的监听
  17. log4j的NDC/MDC区别与应用
  18. Centos下给PHP一键升级高版本7.2.0
  19. JS中constructor与prototype关系概论
  20. Ubuntu14.04下安装glog

热门文章

  1. Kubernetes---资源控制器
  2. 2019南昌网络赛  I. Yukino With Subinterval 树状数组套线段树
  3. 深入理解C++11 C3
  4. Codeforces 718A Efim and Strange Grade 程序分析
  5. Photon Server 实现注册与登录(四) --- 服务端响应登陆和注册
  6. php 求两个数组的差集应该注意的事情
  7. 测试工作小工具~总结&amp;下载连接
  8. C++性能榨汁机之无锁编程
  9. sipp如何避免dead call
  10. 第七章、Ajango自带auth模块