FJOI2007轮状病毒行列式递推详细证明

题目给了你一个奇怪的图，让你求它的生成树个数。

开始写了一个矩阵树：

#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为奇数，偶数可以同样算出。

我们选择第一行消下去，得到的式子中有这么一项：

|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;

}

/*

*/

巴特西

FJOI2007轮状病毒行列式递推详细证明

最新文章

热门文章

巴特西

FJOI2007轮状病毒 行列式递推详细证明

最新文章

热门文章

FJOI2007轮状病毒行列式递推详细证明