傳送門

有向圖生成樹計數 （度數 ->入度->外向樹）

BEST定理?（不定起點的歐拉回路個數=某點為根的外向樹個數（存在歐拉回路->每個點為根的外向樹個數相等）*（每個點的度數（存在歐拉回路->每個點入度=出度）-1）的階層）

一個題解的傳送門

1 //Achen 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdlib> 6 #include<vector> 7 #include<cstdio> 8 #include<queue> 9 #include<cmath> 10 #include<set> 11 #include<map> 12 #define Formylove return 0 13 #define For(i,a,b) for(int i=(a);i<=(b);i++) 14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--) 15 const int N=505,p=998244353; 16 typedef long long LL; 17 typedef double db; 18 using namespace std; 19 LL n,d[N][N],fac[8000007],in[N],out[N]; 20 21 template<typename T>void read(T &x) { 22 char ch=getchar(); x=0; T f=1; 23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); 24 if(ch=='-') f=-1,ch=getchar(); 25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f; 26 } 27 28 LL a[N][N]; 29 LL gauss(int n) { 30 For(i,1,n) For(j,1,n) (a[i][j]+=p)%=p; 31 LL rs=1,f=1; 32 For(i,1,n) { 33 For(j,i+1,n) { 34 LL A=a[i][i],B=a[j][i]; 35 while(B) { 36 LL t=A/B; A%=B; swap(A,B); 37 For(k,i,n) a[i][k]=(a[i][k]-t*a[j][k]%p+p)%p; 38 For(k,i,n) swap(a[i][k],a[j][k]); f=-f; 39 } 40 } 41 rs=rs*a[i][i]%p; 42 } 43 if(f==-1) rs=(p-rs)%p; 44 return rs; 45 } 46 47 LL ksm(LL a,LL b) { 48 LL rs=1,bs=a%p; 49 while(b) { 50 if(b&1) rs=rs*bs%p; 51 bs=bs*bs%p; 52 b>>=1; 53 } 54 return rs; 55 } 56 57 int main() { 58 #ifdef ANS 59 freopen(".in","r",stdin); 60 freopen(".out","w",stdout); 61 #endif 62 fac[0]=1; int cas=0; 63 For(i,1,1000000) fac[i]=fac[i-1]*i%p; 64 while(~scanf("%lld",&n)) { 65 cas++; 66 For(i,1,n) in[i]=out[i]=0; 67 For(i,1,n) For(j,1,n) a[i][j]=0; 68 For(i,1,n) For(j,1,n) { 69 read(d[i][j]); 70 a[i][j]-=d[i][j]; 71 a[j][j]+=d[i][j]; 72 (out[i]+=d[i][j])%=p; 73 (in[j]+=d[i][j])%=p; 74 } 75 int fl=0; 76 For(i,1,n) if(in[i]!=out[i]) { 77 fl=1; break; 78 } 79 if(fl) { 80 printf("Case #%d: 0\n", cas); 81 continue; 82 } 83 For(i,2,n) For(j,2,n) a[i-1][j-1]=a[i][j]; 84 LL ans=gauss(n-1); 85 For(i,2,n) 86 ans=ans*fac[in[i]-1]%p; 87 ans=ans*fac[in[1]]%p; 88 For(i,1,n) For(j,1,n) if(d[i][j]) 89 ans=ans*ksm(fac[d[i][j]],p-2)%p; 90 printf("Case #%d: %lld\n",cas,ans); 91 } 92 Formylove; 93 } 94 /* 95 5 96 0 1 0 0 0 97 0 0 1 0 4 98 0 0 0 5 0 99 1 5 0 0 0 100 0 0 0 1 0 101 */ View Code

?

轉載于:https://www.cnblogs.com/Achenchen/p/9499687.html

總結

以上是生活随笔為你收集整理的HDU 6064 RXD and numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。