【UVA1645】Count

找递推式。

设 \(f_i\) 为 \(i\) 个节点的满足要求的树的数量，由于同一深度下每个节点子树相同，那么也就是说，根节点的若干个儿子都要分到同样的节点数。

设总共有 \(m\) 个儿子，显然这些儿子要分 \(n-1\) 个节点（扣掉根节点），至于这些子树中的分配就交给这些儿子做。

则有递推式 \(f_i=\sum f_j\)，\(j\) 要为 \(n-1\) 的因子。

你也可以把他理解成动态规划方程。注意边界条件 \(f_1=1\)

接下来直接敲代码。

#include <stdio.h>
int f[10005];
const int maxn=10000,mod=1000000007;
int main()
{

	int i,j,n,id(1);
	f[1]=1;
	for(i=2;i<=maxn;++i)
	{
		for(j=1;j<i;++j)
		{
			if((i-1)%j==0)
			{
				(f[i]+=f[j])%=mod;
			}
		}
	}
	while(~scanf("%d",&n))
	{
		printf("Case %d: %d\n",id++,f[n]);
	}
	return 0;
}

但是此题 \(n\le 1000\)，这个 \(n^2\) 的代码可以通过。

那如果 \(n\le10^5\) 呢？

回顾上面的代码，我们发现分解时的 \(O(n)\) 复杂度可以再度优化。

#include <stdio.h>
int f[10005];
const int maxn=10000,mod=1000000007;
int main()
{
	int n,i,j,mid,id(1);
	f[1]=1;
	for(i=2;i<=maxn;++i)
	{
		mid=i-1;
		for(j=1;j*j<mid;++j)
		{
			if(mid%j==0)
			{
				(f[i]+=f[j])%=mod;
				(f[i]+=f[mid/j])%=mod;
			}
		}
		if(j*j==mid)
		{
			(f[i]+=f[j])%=mod;
		}
	}
	while(~scanf("%d",&n))
	{
		printf("Case %d: %d\n",id++,f[n]);
	}
	return 0;
}

按照如上的写法，复杂度降为 \(n\sqrt n\)，即使 \(n\le 10^5\) 也不虚。

如果预处理 \(n\) 以内的质数，复杂度还能再降一点。