题目链接
题目给了你一个奇怪的图，让你求它的生成树个数。
开始写了一个矩阵树：
#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('\n');
}
}; 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;
}
/* */
