Luogu P4336 [SHOI2016]黑暗前的幻想乡 矩阵树定理+容斥原理
2024-09-05 07:26:35
真是菜到爆炸。。。。容斥写反(反正第一次写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
最新文章
- jsp的三种自定义标签 写法示例
- 【HTML5】audio音频
- 如何拷贝CMD命令行文本到粘贴板
- Java 图片提取RGB数组 RGBOfCharMaps (整理)
- 用java开发的网站或者程序
- Struts2 DMI的使用
- 使用F#开发量化模型都缺什么?
- css布局理解
- laravel使用多个数据库连接
- cocos2d Android.mk自动添加类
- 迷宫问题 (bfs广度优先搜索记录路径)
- Spring Cloud Zuul 中文文件上传乱码
- ArrayList与List性能测试
- <;yii 框架学习>; yii 框架改为中文提示
- [javascript] Promise简单学习使用
- 科学计算三维可视化---Traits属性的监听
- log4j的NDC/MDC区别与应用
- Centos下给PHP一键升级高版本7.2.0
- JS中constructor与prototype关系概论
- Ubuntu14.04下安装glog