【BZOJ4596】[Shoi2016]黑暗前的幻想乡

Description

幽香上台以后,第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市,之间原来没有任何路。幽香向选民承诺要减税,所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司,每个建筑公司都想在修路的过程中获得一些好处。
虽然这些建筑公司在选举前没有给幽香钱,幽香还是打算和他们搞好关系,因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边,然后每条边都交给一个能够负责该边的建筑公司修建,并且每个建筑公司都恰好修一条边。
幽香现在想要知道一共有多少种可能的方案呢?两个方案不同当且仅当它们要么修的边的集合不同,要么边的分配方式不同。

Input

第一行包含一个正整数 N(N<=17), 表示城市个数。
接下来 N-1 行,其中第 i行表示第 i个建筑公司可以修建的路的列表:
以一个非负数mi 开头,表示其可以修建 mi 条路,接下来有mi 对数,每对数表示一条边的两个端点。其中不会出现重复的边,也不会出现自环。

Output

仅一行一个整数,表示所有可能的方案数对 10^9 + 7 取模的结果。

Sample Input

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

Sample Output

17

题解:可以采用2^n的容斥原理,暴力枚举每个公司选或不选,然后将这些公司的边放到一起,用矩阵树定理求出方案数。那么答案就是:

可能全选的-至少不选1个的+至少不选2个的-。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll P=1000000007;
ll ans;
int n,S;
vector<int> pa[20],pb[20];
ll v[20][20];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
ll calc()
{
int i,j,k;
ll A,B,tmp,temp,ret=1;
memset(v,0,sizeof(v));
for(i=1;i<n;i++) if((S>>(i-1))&1) for(j=0;j<(int)pa[i].size();j++)
A=pa[i][j],B=pb[i][j],v[A][B]--,v[B][A]--,v[A][A]++,v[B][B]++;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(v[i][j]<0) v[i][j]+=P;
for(i=1;i<n;i++)
{
for(j=i+1;j<n;j++)
{
A=v[i][i],B=v[j][i];
while(B)
{
tmp=A/B,temp=A,A=B,B=temp%B;
for(ret=P-ret,k=i;k<n;k++) v[i][k]=(v[i][k]-tmp*v[j][k]%P+P)%P,swap(v[i][k],v[j][k]);
}
}
ret=ret*v[i][i]%P;
}
return ret;
}
void dfs(int x,int f)
{
if(x==n)
{
ans=(ans+f*calc())%P;
return ;
}
S|=1<<(x-1),dfs(x+1,f);
S^=1<<(x-1),dfs(x+1,-f);
}
int main()
{
n=rd();
int i,a;
for(i=1;i<n;i++)
{
a=rd();
while(a--) pa[i].push_back(rd()),pb[i].push_back(rd());
}
dfs(1,1);
ans=(ans+P)%P;
printf("%lld",ans);
return 0;
}

最新文章

  1. abort 用法讨论
  2. Visual Studio命令行工具
  3. session 学习
  4. sqlserver的执行计划
  5. 【Spark学习】Apache Spark作业调度机制
  6. Android 输入法键盘和activity页面遮挡问题解决
  7. django笔记1
  8. openSuse快捷键
  9. JAVA获取计算机CPU、硬盘、主板、网络等信息
  10. IPC$概念及入侵方式研究
  11. 在IIS中如何配置SSL(https)
  12. MyBatis通过Mapper动态代理来实现curd操作
  13. 我发起并创立了一个 Javascript 前端库 开源项目 jWebForm
  14. PHP中$_POST和$_GET的用法
  15. python---ORM之SQLAlchemy(3)外键与relationship的关系
  16. day5 五、数字类型、字符串,列表类型的基本操作和内置方法
  17. cocos 搭建安卓环境
  18. 半透明全屏蒙层+全屏屏蔽+内容居中+css
  19. sklearn算法库的顶层设计
  20. stdlib.h

热门文章

  1. C# Oracle.ManagedDataAccess 批量更新表数据
  2. 自己动手写CPU之第五阶段(2)——OpenMIPS对数据相关问题的解决措施
  3. pandas所占内存释放
  4. struts和spring整合
  5. 在Visual Studio 2013顯示SCSS詳細錯誤訊息
  6. log4j DatePattern 解惑
  7. 使用jquery dialog
  8. html-loldemo
  9. 把以逗号分隔的字符串转换成list
  10. java代理模式及动态代理类