3659: Which Dreamed It
Time Limit: 20 Sec Memory Limit: 1024 MB
Submit: 134 Solved: 41Description
有n个房间，每个房间有若干把钥匙能够打开特定房间的门。你会做这么件事情：最初你在房间1。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。你希望：最终回到房间1，且垃圾桶中有所有的钥匙。求方案数。两组方案不同，当且仅当使用钥匙的顺序不同。注意，每把钥匙都是不同的。Input
有多组数据。对于每组数据第一行输入一个数n，表示房间数。接下来n行依次描述每个房间：首先一个数s，表示这个房间的钥匙数目，接下来s个数，分别描述每把钥匙能够打开的房间的门。输入以n-0结尾。Output
对于每组数据，输出方案数，为了方便你的输出，请将答案对1000003取模。Sample Input
1
0
2
1 1
1 2
0Sample Output
1
0HINT
在第一组样例中，没有钥匙，则方案数为1。
在第二组样例中，你不可能使用第二个房间的钥匙，所以方案数为0。
房间数小于等于100，钥匙数小于等于200000。
数据组数也不是特别多。
Source
【分析】
这种题叫做结论题。
%CA爷
然后这里有两个结论
1.有向图以i为根的树形图的数目=基尔霍夫矩阵去掉第i行和第i列的主子式的行列式的值(即Matrix-Tree定理不仅适用于求无向图生成树数目,也适用于求有向图树形图数目)
2.以某个点为起点的欧拉回路数=该点为根的树形图数*(所有点出度-1)的乘积(本名BEST theorem)
关于BEST theorem可以提供一个wiki上的讲解:about BEST theorem
最后还有乘上起点的出度？【怎么没说。。
【我觉得我Mod那里应该有问题，但是我没有被卡哦。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int Mod=;
#define Maxn 1000010 int a[][],m[],fac[Maxn]; int qpow(int x,int b)
{
x%=Mod;
int ans=;
while(b)
{
if(b&) ans=1LL*ans*x%Mod;
x=1LL*x*x%Mod;
b>>=;
}
return ans;
} int gauss(int n)
{
if (n==) return ;
int ans=;
for(int i=;i<=n;i++)
{
int t=i;
for(int j=i+;j<=n;j++) if(a[j][i]>a[t][i]) t=j;
if(a[t][i]==) return ;
if(t!=i)
{
ans=-ans;
for(int j=;j<=n;j++) swap(a[t][j],a[i][j]);
}
int ny=qpow(a[i][i],Mod-);
for(int j=i+;j<=n;j++)
{
int nw=1LL*ny*a[j][i]%Mod;
for(int k=i;k<=n;k++) a[j][k]-=1LL*a[i][k]*nw%Mod,a[j][k]=(a[j][k]%Mod+Mod)%Mod;
}
}
for(int i=;i<=n;i++) ans=1LL*ans*a[i][i]%Mod;
ans=(ans%Mod+Mod)%Mod;
return ans;
} int main()
{
int n;
fac[]=;for(int i=;i<=Mod;i++) fac[i]=1LL*fac[i-]*i%Mod;
while()
{
scanf("%d",&n);
if(!n) break;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
scanf("%d",&m[i]);
for(int j=;j<=m[i];j++)
{
int x;
scanf("%d",&x);
if(i!=x) a[i][x]--,a[i][i]++;
}
}
if(n==&&!m[]) {printf("1\n");continue;}
int ans=;
for(int i=;i<=n;i++) ans=1LL*ans*fac[m[i]-]%Mod;
ans=1LL*ans*m[]%Mod;
ans=1LL*ans*gauss(n-)%Mod;
printf("%d\n",ans);
}
return ;
}
2017-04-16 20:11:07