BZOJ 1002: [FJOI2007]轮状病毒

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

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

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

Input

第一行有 1 个正整数 n

Output

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

Sample Input

3

Sample Output

16

Solution

这道题的正解是基尔霍夫矩阵，推出 $f_i=f_{i-1}\times 3-f_{i-2}+2$，然而我这等蒟蒻肯定是不知道怎么证的。

下面是我的做法：
首先去掉外面的某条边，图就变成了类似于这样的结构：

可行解就类似于下图：

我们将未与中心节点相连的点标 0，相连的标 1，删去的边也标 1，每个解就变成了一个 01 串。

假设某个解最外面一共去掉 $k$ 条边，那么这个 01 串长度为 $n+k-1$，共有 $2k-1$ 个 1，而由于向上的边与删去的边交替出现，每个解一定与每个 01 串一一对应，所以最外层去掉 $k$ 条边时，解的个数为 $\binom{n+k-1}{k\cdot 2-1}$。
由于固定了某条边必须去掉，这里只求出了总情况数的 $\frac k n$，所以还需要乘上 $\frac n k$，最后的结果就是这样的：
$\sum_k^n \binom{n+k-1}{k\cdot 2-1}\cdot\frac{n}{k}$。

考虑到高精度大约要 $O(n)$，时间复杂度 $O(n^3)$。 记录上一个 $\binom{n+k-1}{k\cdot 2-1}$，可以优化到 $O(n^2)$。

然而这种数据范围为什么不打表。。

Code

#include<cstdio>

#define cas 10000000
#define maxnum 100

int x[maxnum],y[maxnum],tmp[maxnum+1];

inline void mul(int a)
{
    tmp[0]=0;
    for(int i=0;i<maxnum;i++)
    {
        y[i]*=a;
        y[i]+=tmp[i];
        tmp[i+1]=y[i]/cas;
        y[i]%=cas;
    }
}

inline void div(int a)
{
    for(int i=maxnum-1;i>=0;i--)
    {
        if(i)y[i-1]+=y[i]%a*cas;
        y[i]/=a;
    }
}

inline void c(int a,int b)
{
    if(b>a/2)b=a-b;
    for(int i=0;i<maxnum;i++)y[i]=0;
    y[0]=1;
    for(int i=a;i>a-b;i--)mul(i);
    for(int i=2;i<=b;i++)div(i);
}

inline void print(int *k)
{
    bool is0=true;
    for(int i=maxnum-1;i>=0;i--)
    {
        if(is0&&k[i])
        {
            is0=false;
            printf("%d",k[i]);
        }
        else if(!is0)
        {
            printf("%07d",k[i]);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        c(n+i-1,2*i-1);
        mul(n);
        div(i);
        for(int i=0;i<maxnum;i++)
        {
            x[i]+=y[i];
            if(x[i]>cas)x[i]-=cas,x[i+1]++;
        }
    }
    print(x);
    return 0;
}

日期： 2016-09-07

标签： BZOJ 高精度 找规律

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/3/ 查看。