BZOJ 1002: [FJOI2007]轮状病毒 September 7, 2016 ###Description 轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 ![bzoj1002.p1.png][1] N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示 ![bzoj1002.p2.png][2] 现给定n(N<=100)，编程计算有多少个不同的n轮状病毒 ###Input 第一行有1个正整数n ###Output 计算出的不同的n轮状病毒数输出 ###Sample Input 3 ###Sample Output 16 ###Solution 这道题的正解是基尔霍夫矩阵，推出f[i]=f[i-1]*3-f[i-2]+2，然而我这等蒟蒻肯定是不知道怎么证的 下面是我的做法： 首先去掉外面的某条边，图就变成了类似于这样的结构： ![bzoj1002-1.png][3] 可行解就类似于下图： ![bzoj1002-2.png][4] 我们将未与中心节点相连的点标0，相连的标1，删去的边也标1，每个解就变成了一个01串 假设某个解最外面一共去掉k条边，那么这个01串长度为n+k-1，共有2k-1个1，而由于向上的边与删去的边交替出现，每个解一定与每个01串一一对应，所以最外层去掉k条边时，解的个数为 $$C(n+k-1,k\cdot 2-1)$$。 由于固定了某条边必须去掉，这里只求出了总情况数了k/n，所以还需要乘上n/k，最后的结果就是这样的： $$\sum_k^n C(n+k-1,k\cdot 2-1)\cdot\frac{n}{k}$$ 考虑到高精度大约要O(n)，时间复杂度O(n^3) 记录上一个 $$C(n+k-1,k\cdot 2-1)$$，可以优化到O(n^2) <del>然而这种数据范围为什么不打表。。</del> ###Code ```c++ #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; } ``` [1]: /usr/uploads/2016/09/2454961388.png [2]: /usr/uploads/2016/09/212298548.png [3]: /usr/uploads/2016/09/3955661276.png [4]: /usr/uploads/2016/09/3098156740.png [5]: /usr/uploads/2016/09/1992184554.gif [6]: /usr/uploads/2016/09/1288349390.gif [7]: /usr/uploads/2016/09/1992184554.gif