清华集训2012 数树
数学 计数    2016-12-13 17:05:45    163    0    0
jszyxw   数学 计数

A1287. 数树

时间限制:1.0s   内存限制:512.0MB   
总提交次数:232   AC次数:34   平均分:46.21

问题描述

  小强不像他的朋友阿米巴那样热爱化学;相反,小强最喜欢的事情是数数,特别有的时候喜欢数树。
  小强发现来自自然界的一类无根树很特别:它们的所有非叶子节点的度数都是一样的。小强管这种无根树叫做正则无根树。例如,14个点的度数限制为4的正则无根树有以下2种:


  小强想数N个点的度数限制为M的正则无根树有多少种。在热爱化学的阿米巴的怂恿下,小强把M的范围限制在了4以下,至于这么做在化学、量子物理学和哲学上的理由,小强至今没有搞懂。
  现在,你要写程序来满足小强数树的愿望。

输入格式

  一行用短线(减号)连接的两个整数N和M。

输出格式

  一行,表示N个点的度数限制为M的正则无根树的个数。保证这个数不是0。

数据规模和约定

  对于所有的测试点,1<=N,1<=M,保证答案不是0。
  对于第1个测试点,M=1
  对于第2个测试点,M=2
  对于第3~5个测试点,M=3,N<=202,其中,对于第3、4个测试点,N<=22
  对于第6~9个测试点,M=4,N<=902,其中,对于第6个测试点,N<=32
  对于第10个测试点,N=6002,M=4。
  一共10个测试点

Solution

当m=4时,问题就是求烷烃的同分异构体个数T_T

 

容易把问题转化为:求每个点度数小于等于m,有(n-2)/(m-1)个点的无标号无根树的个数

 

我们首先考虑计算有根树的数量

 
其中的组合数是可重集计数
 
然后再考虑无根树
显然一棵树的当有奇数个点时只可能有一个重心
偶数个点时可能有两个相邻的重心
当只有一个重心时,我们限制转移时size<n/2
当有两个重心时,我们可以看作选择两个大小为N/2的点相接
 

答案很大,要写高精度
复杂度O(N2M2)
还要乘上高精度的复杂度
最后一个点是提答点。。
 

Source Code

int n;
int m;
Big dp[2005][5];

void exec()
{
    read(n), read(m);

    if (m <= 2) {
        write(1);
        return;
    }

    if (n == 6002) {
        puts("460553657800537381989527076988790838635967792988400941907807811114671802405199766576463202911863031096578661549297753720003008335656879425034460729281964424706881882421666981034969349224199533622070089644457233223224152176118054829241290258392602989371497364114082958579710103586940267689559169088592271926842603782285565835844922567934706687092021712340833071287930332138144098357332357510198556706829927676388162304302050571820405421820166284290749556972087256171440570212114946523605235375506738828016015280539643828578568550580618029211018596396266862876674830494216456169166513635252534055513691414680914928389800044070410746942242607505840210680481044969836339392429246949035960847037306894511585670557328078740769225801436712030001756685659802096264546304375240098639287859033797402038347986736701326175217951359362785202565738081172698363317702430905743880911668210777061802350870067");
        return;
    }

    n = (n - 2) / (m - 1);


    dp[1][0] = 1;
    for (int size = 1; size <= (n - 1) / 2; ++ size) {

        Big s = 0;

        for (int i = 0; i < m; ++ i)
            s += dp[size][i];

        for (int i = n; i > size; -- i)
            for (int j = 1; j <= m; ++ j)
                for (int k = 1; k <= j && size * k < i; ++ k)
                    dp[i][j] += dp[i - size * k][j - k] * C(s + (k - 1), k);
    }

    Big ret = 0;
    for (int i = 0; i <= m; ++ i) ret += dp[n][i];
    if (n % 2 == 0) {
        Big ret2 = 0;
        for (int i = 0; i < m; ++ i) ret2 += dp[n / 2][i];
        ret += C(ret2 + 1, 2);
    }

    std::cout << ret << std::endl;
}
 
 
参考链接:

 

BZOJ3196: Tyvj 1730 二逼平衡树
163 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航