注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj1005  

2013-01-23 12:34:51|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

明明的烦恼:

这就又要用到一个诡异的树的prufer编码了……

总之就是每一个树都与一个prufer编码一一对应,然后prufer编码里的数出现的个数正好是树的这个点的度数减1。

这道题只要把prufer编码构造出来,就必定能把树构造出来。

然后根据组合公式做。

假设sum=Σd[i]-1,我们先选sum个位置填数有C(n-2,sum),由于有重复所以要去重,也就是计算可重排列的公式:

“可重排列:
K种元素,重数分别为n1,n2,…,nk,所有n=Σni个元素的全排列数为n!/(n1!n2!..nk!)”

代入进去。
然后剩下n-2-sum个位置随你乱填但不能填度数已知的点。假如p个点的度数未知,就是  p^(n-2-sum)个方案了,然后再乘一下。

然后高精度。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MOD 100000
using namespace std;
int n,m,sum,degree[1010];
struct Big_numbers
{
    int digit[3010],len;
    void operator *= (int p)
    {
        int jinwei=0;
        for(int i=1;i<=len;i++)
        {
            digit[i]=digit[i]*p+jinwei;
            jinwei=digit[i]/MOD;
            digit[i]%=MOD;
        }
        if(jinwei)  digit[++len]=jinwei;
    }
    void operator /= (int p)
    {
        int now=0,temp;
        for(int i=len;i>=1;i--)
            temp=digit[i],digit[i]=(now*MOD+temp)/p,now=(now*MOD+temp)%p;
        for(;len>1&&digit[len]==0;len--);
    }
    void print()
    {
        printf("%d",digit[len]);
        for(int i=len-1;i>=1;i--)
        {
            for(int j=MOD/10;j>digit[i]&&j>=10;j/=10)
                printf("0");
            printf("%d",digit[i]);
        }
        printf("\n");
    }
}ans;
void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&degree[i]);
        degree[i]==-1?m++:sum=sum+degree[i]-1;
    }
}
void work()
{
    ans.len=1,ans.digit[1]=1;
    if(n-2<sum)
    {
        ans.digit[1]=0;
        return ;
    }
    for(int i=1;i<=n-2-sum;i++)
        ans*=m;
    for(int i=n-2;i>sum;i--)
        ans*=i,ans/=(n-i-1);
    for(int i=1;i<=sum;i++)
        ans*=i;
    for(int i=1;i<=n;i++)
        if(degree[i]!=-1)
            for(int j=1;j<=degree[i]-1;j++)
                ans/=j;
}
int main()
{
    read();
    work();
    ans.print();
    return 0;
}
  评论这张
 
阅读(688)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017