锐客网

  1. 首页 > it技术 > >

Matrix-Tree定理|[BEST定理 矩阵树定理] BZOJ 3659 Which Dreamed It

【Matrix-Tree定理|[BEST定理 矩阵树定理] BZOJ 3659 Which Dreamed It】BEST theorem
一个证明？
注意区分下题目中要求的“欧拉回路”的条数和定理中欧拉回路的条数
欧拉回路是个回路 所以存在循环同构
题中要求起点是1 实际上还要乘上1的度数 因为从1的任一边出发在题中都算作一种不同方案

#include #include #include using namespace std; typedef long long ll; const int N=105; const int P=1000003; int n; char s[N][N]; ll fac[200005]; inline ll Pow(ll a,int b){ ll ret=1; for (; b; b>>=1,a=a*a%P) if (b&1) ret=ret*a%P; return ret; } inline ll Inv(ll a){ return Pow(a,P-2); }int a[N][N]; inline int det(int n){ int f=0; for (int i=1; i<=n; i++){ int k=0; for (int j=i; j<=n; j++) if (a[j][i]) {k=j; break; } if (i^k) { for (int j=i; j<=n; j++) swap(a[i][j],a[k][j]); f^=1; } for (int j=i+1; j<=n; j++){ ll t=(ll)Inv(a[i][i])*a[j][i]%P; for (int k=i; k<=n; k++) (a[j][k]+=P-(ll)t*a[i][k]%P)%=P; } } ll ret=1; for (int i=1; i<=n; i++) ret=ret*a[i][i]%P; return f?(P-ret)%P:ret; }#define read(x) scanf("%d",&(x))int deg[N]; int main(){ int x,k; freopen("t.in","r",stdin); freopen("t.out","w",stdout); fac[0]=1; for (int i=1; i<=200000; i++) fac[i]=fac[i-1]*i%P; while (1){ read(n); if (!n) break; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j]=0; for (int i=1; i<=n; i++){ read(k); deg[i]=k; while (k--){ read(x); if (i^x) a[n-i+1][n-x+1]--,a[n-x+1][n-x+1]++; } } if (n==1) { printf("%lld\n",fac[deg[1]]); continue; } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j]=(P+a[i][j])%P; ll ans=(ll)det(n-1)*deg[1]%P; for (int i=1; i<=n; i++) ans=ans*fac[deg[i]-1]%P; printf("%lld\n",ans); } return 0; }

    推荐阅读


    上一篇：数学——离散概率|例题10-16 过河 UVa12230

    下一篇：koa中使用sequelize