[FJOI2007]轮状病毒

1002: [FJOI2007]轮状病毒

Time Limit: 1 Sec Memory Limit: 162 MB
[Submit][Status][Discuss]

Description

　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示

　　现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

Input

　　第一行有1个正整数n

Output

　　计算出的不同的n轮状病毒数输出

Sample Input

Sample Output

每种n轮状病毒对应着一种不同的生成树

同样，n+1个点的生成树对应着不同的n轮状病毒

所以 n轮状病毒的种数 ==

n+1个点，已知每个点可以连出的边的生成树的个数

现在问题转化为求生成树的个数

矩阵树定理即可

但是不写高精只能做到50分

然后你可以根据这个打表找出规律（我没找出来）

f[i]=3*f[i-1]-f[i-2]+2

再写个高精就A了

矩阵树定理打表代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int C[101][101];
int n;
void Matrix_tree()
{
    memset(C,0,sizeof(C));
    if(n==1)
    {
        C[0][0]=C[1][1]=1;
        C[0][1]=C[1][0]=1;
    }
    else if(n==2)
    {
        C[0][0]=2;
        C[1][1]=C[2][2]=3;
        C[0][1]=C[0][2]=C[1][0]=C[2][0]=1;
        C[1][2]=C[2][1]=2;
    }
    else
    {
        C[0][0]=n;
        for(int i=1;i<=n;i++) C[i][0]=C[0][i]=1;
        for(int i=1;i<=n;i++) C[i][i]=3;
        C[1][2]=C[1][n]=1;
        C[n][n-1]=C[n][1]=1;
        for(int i=1;i<n;i++) C[i][i-1]=C[i][i+1]=1;
    }
    LL ans=1,t;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
            while(C[j][i])
            {
                t=C[i][i]/C[j][i];
                for(int k=i;k<=n;k++) C[i][k]-=C[j][k]*t;
                for(int k=i;k<=n;k++) swap(C[i][k],C[j][k]);
                ans=-1;
            }
        ans*=C[i][i];
    }
    if(ans<0) ans=-ans;
    cout<<ans<<endl;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    Matrix_tree();
}

AC代码

#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int len;
    int num[1001];
    node() { len=0; memset(num,0,sizeof(num)); } 
    node operator * (int p) const
    {
        node a;
        for(int i=1;i<=len;i++) 
        a.num[i]=num[i]*p;
        for(int i=1;i<=len;i++) a.num[i+1]+=a.num[i]/10,a.num[i]%=10;
        a.len=len;
        while(a.num[a.len+1]) a.len++;
        return a; 
    }
    node operator - (node p)
    {
        node a;
        for(int i=1;i<=len;i++) a.num[i]=num[i];
        for(int i=1;i<=len;i++) 
        {
            if(a.num[i]<p.num[i]) a.num[i]+=10,a.num[i+1]--;
            a.num[i]=a.num[i]-p.num[i];
        }
        a.len=len;
        while(len && !a.num[a.len]) len--;
        return a;
    }
    node operator + (int p)
    {
        node a;
        a.num[1]=num[1]+2;
        for(int i=2;i<=len;i++) a.num[i]=num[i];
        for(int i=1;i<=len;i++)
            if(a.num[i]>=10) a.num[i+1]++,a.num[i]-=10;
        a.len=len;
        if(a.num[len+1]) a.len++;
        return a;
    }
    void operator = (node p)
    {
        this->len=p.len;
        for(int i=1;i<=p.len;i++) this->num[i]=p.num[i];
    } 
    void print()
    {
        for(int i=len;i;i--) printf("%d",num[i]);
    }
};
node f[101];
int main()
{
    int n;
    scanf("%d",&n);
    f[1].len=f[2].len=1;
    f[1].num[1]=1; f[2].num[1]=5;
    for(int i=3;i<=n;i++) f[i]=f[i-1]*3-f[i-2]+2;
    f[n].print();
}