logo在线设计网站,wordpress安装插件ftp,安徽省建设工程质量管理办法,司法厅网站建设方案https://www.lydsy.com/JudgeOnline/problem.php?id4596 https://www.luogu.org/problemnew/show/P4336#sub 四年一度的幻想乡大选开始了#xff0c;最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡#xff0c;扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪#…https://www.lydsy.com/JudgeOnline/problem.php?id4596 https://www.luogu.org/problemnew/show/P4336#sub 四年一度的幻想乡大选开始了最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪人类博丽灵梦和八云紫等人整日高谈所有妖怪平等幻想乡多元化等等对于幻想乡目前面临的种种大问题却给不出合适的解决方案。 风间幽香是幻想乡里少有的意识到了问题的严重性的大妖怪。她这次勇敢的站了出来参加幻想乡大选。提出包括在幻想乡边境建墙并让人类出钱大力开展基础设施建设挽回失业率等一系列方案成为了大选年出人意料的黑马并顺利的当上了幻想乡的大统领。 幽香上台以后第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市之间原来没有任何路。幽香向选民承诺要减税所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司每个建筑公司都想在修路的过程中获得一些好处。虽然这些建筑公司在选举前没有给幽香钱幽香还是打算和他们搞好关系因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。 每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边然后每条边都交给一个能够负责该边的建筑公司修建并且每个建筑公司都恰好修一条边。 幽香现在想要知道一共有多少种可能的方案呢两个方案不同当且仅当它们要么修的边的集合不同要么边的分配方式不同。 看了矩阵树教程它让我做这道题http://www.cnblogs.com/zj75211/p/8039443.html。 深感自己老龄化严重。 n17显然是要压状态了那我们只能压是否选择每个公司来建边了……好像和题意不符啊。 但是思考事实上我们要求的东西可以通过容斥来表达出来即不考虑哪些公司建哪些边我加所有公司的边的方案数-我少一个公司的所有边的方案数……最后反正是把所有不合法的方案都剔除出去了。 那么我们枚举状态用矩阵树定理求出生成树个数就是方案了之后再加加减减就行了。 #includecstdio
#includequeue
#includecstring
#includecmath
#includecctype
#includealgorithm
using namespace std;
typedef long long ll;
const int p1e97;
const int N18;
inline int read(){int X0,w0;char ch0;while(!isdigit(ch)){w|ch-;chgetchar();}while(isdigit(ch))X(X3)(X1)(ch^48),chgetchar();return w?-X:X;
}
ll x[N][N],ans;
ll gauss(int n){ll res1;for(int i1;in;i){for(int ji1;jn;j){while(x[j][i]!0){ll tx[i][i]/x[j][i];for(int ki;kn;k)x[i][k](x[i][k]-x[j][k]*t)%p;for(int ki;kn;k)swap(x[i][k],x[j][k]);res-res;}}if(!x[i][i])return 0;res(res*x[i][i])%p;}return (res%pp)%p;
}
int n,m[N],u[N][N*N],v[N][N*N],d[N];
int main(){nread();for(int i1;in;i){m[i]read();for(int j1;jm[i];j){u[i][j]read(),v[i][j]read();}}for(int i(1(n-1))-1;i0;i--){int tot0;memset(x,0,sizeof(x));memset(d,0,sizeof(d));for(int j1;jn;j){int w(i(j-1))1;if(w){for(int k1;km[j];k){x[u[j][k]][v[j][k]]--;x[v[j][k]][u[j][k]]--;d[u[j][k]];d[v[j][k]];}for(int k1;kn;k)x[k][k]d[k];tot;}}ll tmpgauss(n-1);if((n-1-tot)%20)ans(anstmp)%p;else ans(ans-tmp)%p;}printf(%lld\n,(ans%pp)%p);return 0;
} 本文作者luyouqi233。 欢迎访问我的博客http://www.cnblogs.com/luyouqi233/ 转载于:https://www.cnblogs.com/luyouqi233/p/8980839.html
