题目给了你一个奇怪的图，让你求它的生成树个数。
开始写了一个矩阵树：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<bitset> #include<cmath> #define P puts("lala") #define pc cerr<<"lala"<<endl #define HH puts("") #define pb push_back #define pf push_front #define fi first #define se second #define mkp make_pair using namespace std; inline void read(int &re) { char ch=getchar();int g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar(); re*=g; } typedef long long ll; inline void read(ll &re) { char ch=getchar();ll g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar(); re*=g; } const int N=109; int n; ll kir[N][N]; ll gauss() { ll ans=1; for(int i=1;i<n;++i) { for(int j=i+1;j<n;++j) { while(kir[j][i]) { ll t=kir[i][i]/kir[j][i]; for(int k=i;k<n;++k) { kir[i][k]=kir[i][k]-kir[j][k]*t; swap(kir[i][k],kir[j][k]); } ans=-ans; } } ans=ans*kir[i][i]; } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin);freopen("1.out","w",stdout); #endif int i,j,opt,T; read(n); for(i=0;i<n;++i) { kir[i][i]++;kir[n][n]++; kir[i][n]=-1;kir[n][i]=-1; } for(i=0;i<n;++i) { kir[i][i]++;kir[(i+1)%n][(i+1)%n]++; kir[i][(i+1)%n]=-1;kir[(i+1)%n][i]=-1; } n++; ll ans=gauss(); printf("%lld",abs(ans)); return 0; } /* */
发现答案会超过long long的范围，而用高精好像会T，于是花了几十分钟去推这个基尔霍夫矩阵行列式的递推式。
首先，我们把这个图的基尔霍夫矩阵最后一行最后一列消去，得到这样的矩阵A
|3 -1 0 ... ... 0 -1|
|-1 3 -1 0 ....0 0|
|0 -1 3 -1 0 ... 0|
|... ... ...|
|-1 0... ... ...-1 3 |
现在只需要求这个矩阵的行列式。
我们先假定n为奇数，偶数可以同样算出。
我们选择第一行消下去，得到的式子中有这么一项：
B:
|3 -1 0 ... ... 0 0|
|-1 3 -1 0 ....0 0|
|0 -1 3 -1 0 ... 0|
|... ... ...|
|0 0... ... ...-1 3 |
（注意它在(1,n)与(n,1)的元素与A不一样）
设长，宽为n的上面那个矩阵的行列式为f(n)
把矩阵A第一行消去后，得到3*f(n-1)与矩阵：(为了方便，以n=5为例画出来)
(+)
|-1 -1 0 0|
|0 3 -1 0|
|0 -1 3 -1|
|-1 0 -1 3|
(-)
|-1 3 -1 0|
|0 -1 3 -1|
|0 0 -1 3|
|-1 0 0 -1|
再对两个矩阵消去第一列，其中会得到两个三角矩阵(对角线上全是-1)，直接算出来行列式为-1
得到det(A)=3*f(n-1)-2*f(n-2)-2
于是我们只需算出f(n)
对于f(n)同样的消两次，然后发现除了f(n-1),f(n-2)，剩下的那个矩阵行列式为0(它有一整列都是0)
得到:f(n)=3*f(n-1)-f(n-2)
于是特判n=1,n=2，其余写高精递推即可
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<bitset> #include<cmath> #define P puts("lala") #define pc cerr<<"lala"<<endl #define HH puts("") #define pb push_back #define pf push_front #define fi first #define se second #define mkp make_pair using namespace std; inline void read(int &re) { char ch=getchar();int g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar(); re*=g; } typedef long long ll; inline void read(ll &re) { char ch=getchar();ll g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar(); re*=g; } const int N=109; int n; struct big { int len; int s[100]; big() {clean();} void clean() { memset(s,0,sizeof(s));len=0; } void operator = (int x) { for(;x;x/=10) s[len++]=x%10; } void print() { for(int i=len-1;i>=0;--i) printf("%d",s[i]); putchar(' '); } }; big c; big operator + (big a,big b) { int len=max(a.len,b.len); c.clean(); c.len=len; for(int i=0;i<len;++i) c.s[i]=a.s[i]+b.s[i]; for(int i=0;i<len;++i) c.s[i+1]+=c.s[i]/10,c.s[i]%=10; if(c.s[len]) c.len++; return c; } big operator - (big a,big b)//a > b { c.clean(); for(int i=0;i<a.len;++i) { c.s[i]+=a.s[i]-b.s[i]; if(c.s[i]<0) c.s[i]+=10,a.s[i+1]--; } int len=a.len-1; for(;!c.s[len];len--); c.len=len+1; return c; } big operator * (big a,big b) { int len=a.len+b.len-1; c.clean(); c.len=len; for(int i=0;i<a.len;++i) for(int j=0;j<b.len;++j) c.s[i+j]+=a.s[i]*b.s[j]; for(int i=0;i<len;++i) c.s[i+1]+=c.s[i]/10,c.s[i]%=10; if(c.s[len]) c.len++; return c; } big f[N]; int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin);freopen("1.out","w",stdout); #endif int i,j,opt,T; read(n); f[1]=3;f[2]=8; if(n==1) {printf("1");return 0;} else if(n==2) {printf("5");return 0;} big three,two; three=3;two=2; for(i=3;i<=n;++i) f[i]=three*f[i-1]-f[i-2]; big ans=(three*f[n-1])-(two*f[n-2])-two; ans.print(); return 0; } /* */