根本不知道题面在讲什么 矩阵树定理有向图版本 邻接矩阵还是邻接矩阵 度数矩阵根据是出度还是入度分别计算内向树和外向树
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; const int N=305; const int P=1e9+7; int n; char s[N][N]; 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; } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%s",s[i]+1); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (s[i][j]=='1'){ a[n-i+1][n-j+1]=P-1; a[n-j+1][n-j+1]++; } int ans=det(n-1); printf("%d\n",ans); return 0; }还有个我以前一直以为只能这么做的状压做法
