2014
03-01

# Counting spanning trees

Everyone knows spanning trees, especially MST problem. But most of them are not familiar with degree constrained spanning tree.
a degree-constrained spanning tree is a spanning tree which the maximum vertex degree is limited to a certain constant d.
Given two integers n and d, your task is to count the number of degree constrained spanning trees of a (labeled) complete graph with n vertices.

Each line contains two integers n, d. 1<=n<=100, 1<=k<=100.

Each line contains two integers n, d. 1<=n<=100, 1<=k<=100.

3 1
3 2
4 2
10 3

0
3
12
3458313

从每个数考虑过来，即是每个数最多能被d个位置使用。

这时候就可以得出递推公式：

dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C(k,n-2-(j-k)));

dp[i][j]表示放完第i个数，用掉j个位置总共有多少种方法。

#include<iostream>
using namespace std;
#define MAXN 150
#define MOD 20090829
__int64 dp[MAXN][MAXN],c[MAXN][MAXN];
__int64 a[MAXN];
__int64 b[MAXN];
int gcd(int x,int y)
{
if (y==0) return x;
else return gcd(y,x%y);
}
__int64 C(int k,int n)
{
int i,j;
if (c[k][n]!=0) return c[k][n];
__int64 temp,ans;
for(i=n-k+1;i<=n;i++) a[i]=i;
for(i=1;i<=k;i++) b[i]=i;
for(i=1;i<=k;i++)
for(j=n-k+1;j<=n;j++)
{
temp=gcd(b[i],a[j]);
b[i]/=temp;
a[j]/=temp;
}

ans=1;
for(i=n-k+1;i<=n;i++)
ans=ans*a[i]%MOD;
c[k][n]=ans;
return ans;
}
int min(int x,int y)
{
if (x<y) return x;
else return y;
}
int main()
{
int n,d,i,j,k;
__int64 ans;
memset(c,0,sizeof(c));
while(scanf("%d %d",&n,&d)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=n;i++)
for(j=0;j<=n-2;j++)
for(k=0;k<=min(j,d-1);k++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j-k]*C(k,n-2-(j-k)))%MOD;
}
ans=dp[n][n-2];
printf("%I64d/n",ans);
}
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

3. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count