mcfx's blog - 找规律

mcfx's blog - 找规律 2016-09-08T22:30:00+08:00 Typecho /feed/atom/category/zgl/ <![CDATA[BZOJ 1089: [SCOI2003]严格n元树]]> /archives/17/ 2016-09-08T22:30:00+08:00 2016-09-08T22:30:00+08:00 admin

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

]]> <![CDATA[BZOJ 1002: [FJOI2007]轮状病毒]]> /archives/3/ 2016-09-07T23:02:00+08:00 2016-09-07T23:02:00+08:00 admin

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

]]>