BZOJ 1089: [SCOI2003]严格n元树 September 8, 2016 ###Description 如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d （根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图： ![1.jpg][1] 给出n, d，编程数出深度为d的n元树数目。 ###Input 仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16) ###Output 仅包含一个数，即深度为d的n元树的数目。 ###Sample Input 【样例输入1】 2 2 【样例输入2】 2 3 【样例输入3】 3 5 ###Sample Output 【样例输出1】 3 【样例输出2】 21 【样例输出2】 58871587162270592645034001 ###Solution 我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1) 当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1 ###Code ```c++ #include<cstdio> #include<memory.h> #include<cstring> #define maxnum 100 #define cas 1000000000 int a[maxnum],b[maxnum],t[maxnum],al=1,bl; inline void mul() { memset(t,0,(al+bl+1)*4); for(int i=0;i<al;i++) for(int j=0;j<bl;j++) { long long f=(long long)a[i]*b[j]; t[i+j]+=f%cas; if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++; t[i+j+1]+=f/cas; if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++; } if(t[al+bl-1])al=al+bl;else al=al+bl-1; memcpy(a,t,al*4); } inline void print(int *a) { printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n"); } int main() { int n,d; scanf("%d%d",&n,&d); a[0]=1; while(d--) { memcpy(b,a,al*4); bl=al; for(int i=1;i<n;i++)mul(); a[0]++; for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++; if(a[al])al++; } for(int i=0;i<bl;i++)a[i]-=b[i]; for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--; if(!a[al-1])al--; print(a); printf("\n"); return 0; } ``` [1]: /usr/uploads/2016/09/1813884886.jpg
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