P2144 [FJOI2007]轮状病毒 题解
Post time: 2022-03-04 09:18:38
传送门
感觉还是挺不错的一题。
首先一眼 Matrix-tree，再一看，不取模的话求行列式时的除法我不会弄。所以考虑利用这题的基尔霍夫矩阵推式子。不会矩阵树的话左转 模板
矩阵树定理可以任意扔掉一行一列，在这个题里肯定是扔掉最中间那个点，因为你发现扔掉之后这个矩阵看起来很规律：
\[\begin{bmatrix} 3&-1&0&\cdots&-1\\ -1&3&-1&\cdots&0\\ 0&-1&\ddots&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&-1\\ -1&0&\cdots&-1&3 \end{bmatrix} \]有一个结论说的是：行列式等于它的任一行（列）的各元素与其对应的代数余子式乘积之和。我们首先设大小为 \(n\) 的基尔霍夫矩阵答案为 \(A_n\)。
对于一个元素 \(a_{i,j}\)，它的余子式 \(M_{i,j}\) 等于去掉第 \(i\) 行和第 \(j\) 列之后的行列式的值。它的代数余子式 \(A_{i,j}=(-1)^{i+j}M_{i,j}\)。
由于代数余子式有奇偶性的影响，所以下面推的都是 \(n\) 为奇数的情况。\(n\) 为偶数的情况推导过程也是相似的。
对于这个矩阵，因为两个角上的 \(-1\) 看起来很不爽，考虑把第一行各个元素拿出来用上面的方法求行列式。
对于 \(a_{1,1}\)，删掉之后矩阵为
\[\begin{bmatrix} 3&-1&\cdots&0\\ -1&\ddots&\ddots&\vdots\\ \ddots&\ddots&\ddots&-1\\ 0&\cdots&-1&3 \end{bmatrix} \]这个看起来就很舒服了，我们设大小为 \(n\) 的这样的矩阵的行列式为 \(B_n\)。那么 \(a_{1,1}\) 的贡献为 \(3B_{n-1}\)。
对于 \(a_{1,2}\)，删掉之后矩阵为
\[\begin{bmatrix} -1&-1&\cdots&0\\ 0&3&\ddots&\vdots\\ \vdots&\ddots&\ddots&-1\\ -1&\cdots&-1&3 \end{bmatrix} \]这个还不太好搞，考虑再把第一列的元素拿出来做一次，删去这个新矩阵的 \(a_{1,1}\)，可以得到 \(B_{n-2}\)，贡献为 \(-B_{n-2}\)；删去 \(a_{n-1,1}\)，可以得到一个对角线都为 \(-1\) 的下三角矩阵，它的行列式就是对角线各元素乘积 \(-1\)，贡献就是 \(-1\)。
对于 \(a_{1,n}\) 同理，可以得到贡献也为 \(-B_{n-2}-1\)。
综上可以得到，当 \(n\) 为奇数时，\(A_n=3B_{n-1}-2B_{n-2}-2\)。
同理我们也可以得到 \(n\) 为偶数时递推式不变，也可以得到 \(B\) 的递推式：\(B_n=3B_{n-1}-B_{n-2}\)。联立两个式子可以得到 \(A\) 的递推式：
\[A_n=3A_{n-1}-A_{n-2}+2 \]这个就不需要做高精度除法了，直接做就可以。
点击查看代码
const int N=100+13;
struct Big{
int d[N],len;
Big(){memset(d,0,sizeof d);len=1;}
inline Big operator *(const int &x)const{
Big Ans;
int l=len;
for(int i=1;i<=l;++i) Ans.d[i]=d[i]*x;
for(int i=1;i=10) Ans.d[i+1]+=Ans.d[i]/10,Ans.d[i]%=10;
while(Ans.d[l]>=10) Ans.d[l+1]+=Ans.d[l]/10,Ans.d[l]%=10,++l;
while(l&&!Ans.d[l]) --l;
Ans.len=l;
return Ans;
}
inline Big operator +(const int &x)const{
Big Ans;
int l=len;
Ans.d[1]=d[1]+x;
for(int i=2;i<=l;++i) Ans.d[i]=d[i];
for(int i=1;i=10) Ans.d[i+1]+=Ans.d[i]/10,Ans.d[i]%=10;
while(Ans.d[l]>=10) Ans.d[l+1]+=Ans.d[l]/10,Ans.d[l]%=10,++l;
while(l&&!Ans.d[l]) --l;
Ans.len=l;
return Ans;
}
inline Big operator -(const Big &A){
Big Ans;
int l=len;
for(int i=1;i<=l;++i){
if(d[i]=10) Ans.d[i+1]+=Ans.d[i]/10,Ans.d[i]%=10;
while(Ans.d[l]>=10) Ans.d[l+1]+=Ans.d[l]/10,Ans.d[l]%=10,++l;
while(l&&!Ans.d[l]) --l;
Ans.len=l;
return Ans;
}
};
int main(){
Big A,B;A.d[1]=1;
int n;read(n);
for(int i=2;i<=n;++i){Big tmp=A;A=A*3-B+2,B=tmp;}
for(int i=A.len;i;--i) print(A.d[i]);
return 0;
}