BZOJ1002 [FJOI2007]轮状病毒 【基尔霍夫矩阵和MT定理】

tonyfang posted @ 2015年8月24日 22:25 in BZOJ with tags c++ OI , 293 阅读

首先,恶补了行列式的东西。然后,感谢VFleaKing的帮助,让我理解了这个递推式。

我不知道我的原来的题解坑了多少人……算了不看了,重新来一发。

首先,参照周冬的论文《生成树的计数》,自行理解基尔霍夫矩阵和MatrixTree定理,论文讲了很清楚了。

$基尔霍夫矩阵A=无向图的度数矩阵B-无向图的邻接矩阵C$

$MatrixTree$定理:把基尔霍夫矩阵删去第$r$行第$r$列后,矩阵的行列式的绝对值就是生成树的个数

首先,本题很明显求生成树的个数。

矩阵是这样的(借用VFK的矩阵)(3轮状基)

3  -1   0   0   0 ... 0   0   0 -1
-1  3  -1   0   0 ... 0   0   0 0
0  -1   3  -1  0 ... 0   0   0 0
0   0  -1   3 -1 ... 0   0   0 0
0   0   0  -1   3 ... 0   0   0 0
... ... ... ... ... ... ...  ...
0   0   0   0   0 ... 3 -1   0 0
0   0   0   0   0 ... -1 3 -1 0
0   0   0   0   0 ... 0 -1   3 -1
-1 0   0   0   0 ... 0   0  -1 3
 
对的就是这个矩阵,叫基尔霍夫矩阵。
上面这个设为矩阵A,然后我们再看一个矩阵B:
 
 -1 3 -1   0   0 ... 0   0   0   0
 0 -1   3   -1 0 ... 0   0   0   0
 0   0 -1   3  -1 ... 0   0   0   0
 0   0   0   -1 3 ... 0   0   0   0
 ... ... ... ... ... ... ...  ...
 0   0   0   0   0 ... 3 -1   0   0
 0   0   0   0   0 ... -1 3 -1   0 
 0   0   0   0   0 ... 0 -1   3 -1
-1   0   0   0   0 ... 0   0 -1   3
 3 -1   0   0   0 ... 0   0   0 -1
 
这个矩阵是A矩阵经过$n-1$次变换得到的,所以$A=(-1)^{n-1} \times B$。
我们观察矩阵B,发现左下面三个数很讨厌,如果消掉就是个上三角矩阵了,行列式就是对角线的乘积了。
倒数第二行,用第一行乘$-1$来消去第一个数,变成了
0   -3   1   0   0  ...  0   0  -1   3
再来,用第二行乘$-3$消去第二个数,变成了
0    0  -8   3   0  ...  0   0  -1   3
现在我们看出了点什么,把这个一般化,设正在处理的这一行的第$k$个和第$k+1$个是$F(k)$和$G(k)$,总能找到上面的一行,来乘以$F(k)$消去$F(k)$,这时候,根据假设,应该是$F(k+1)$和$G(k+1)$,那么我们根据这个可以得到2个等式:$F(k+1)=G(k)+3F(k), G(k+1)=-F(k)$,化简后$F(k+1)=3F(k)-F(k-1)$。
经过漫长的消东西,把倒数第二行变成了:
0    0   0   0   0  ...  0   0  F(n-1)-1   G(n-1)+3
这是一个很好的结果啦,马上就上三角矩阵啦!
设$f=F(n-1)-1,g=G(n-1)+3$,那么就变成了:
0    0   0   0   0  ...  0   0  f   g
我们看下倒数第一行,其实是一样的,我们就一直推就好了,设$H(k),I(k)$。
其实和$F,G$的递推式一样的。
其中H(1)=3,H(2)=8.
最后变成了:
0    0   0   0   0  ...  0   0  H(n-1)   I(n-1)-1
设$h=H(n-1),i=I(n-1)-1$,那么就变成了
0    0   0   0   0  ...  0   0  h   i
变成了一个差一点就完美的东西,消去$h$后,容易得到
$A=-f\times i+g+h$
将$f,g,h,i$的值代入,详细见VFK的博客。
$A=H(n)+F(n-1)-2$。
设递推公式$R(n)$,则$R(n)=3R(n-1)-R(n-2)+2$。
感谢VFK:
 
#include<bits/stdc++.h>
using namespace std;
struct bn {
    int len;
    int k[110];
}f[101];
// f(i)=3f(i-1)-f(i-2)+2
bn mul(bn a) {
    bn ans;
    memset(ans.k,0,sizeof(ans.k));
    ans.len=a.len;
    for (int i=1;i<=a.len;++i) {
        ans.k[i]+=a.k[i]*3;
        if (ans.k[i]>=10) {
            ans.k[i+1]+=ans.k[i]/10;
            ans.k[i]%=10;
        }
    }
    if (ans.k[ans.len+1]>0) ans.len++;
    return ans;
}
bn addtwo(bn a) {
    bn ans;
    ans.len=a.len;
    memset(ans.k,0,sizeof(ans.k));
    for (int i=1;i<=ans.len;++i)
        ans.k[i]=a.k[i];
    ans.k[1]+=2;
    int ka=1;
    while(ans.k[ka]>=10) {
        ans.k[ka+1]+=ans.k[ka]/10;
        ans.k[ka++]%=10;
    }
    if (ka>ans.len) ans.len=ka;
    return ans;
}
bn xminus(bn a, bn b) {
    bn ans;
    ans.len=a.len;
    memset(ans.k,0,sizeof(ans.k));
    for (int i=1;i<=a.len;++i) {
        ans.k[i]+=a.k[i]-b.k[i];
        if (ans.k[i] < 0) {
            ans.k[i]+=10;
            ans.k[i+1]--;
        }
    }    
    while(ans.k[ans.len]==0) ans.len--;
    return ans;
}
int main() {
    int n; scanf("%d",&n);
    //for (int i=1;i<=n;++i) memset(f[i].k,0,sizeof(f[i].k));
    f[1].k[1]=1;f[2].k[1]=5;f[1].len=1;f[2].len=1;
    //bn ans=xminus(mul(f[2]),f[1]);
    //for (int i=ans.len;i>=1;--i) printf("%d",ans.k[i]);
    for (int i=3;i<=n;++i) f[i]=addtwo(xminus(mul(f[i-1]),f[i-2]));
    //f[n]=mul(f[2]);
    for (int i=f[n].len;i>=1;--i) printf("%d",f[n].k[i]);
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter