最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • hdu 5136(dp计数)

    题目链接

    题意:求直径为K的每一个点的边数不超过3的结构相互不同构的树有多少种?


    解法:把树的直径拉开,两边就是两棵2叉树了。子问题:1个深度为m的不同构的2叉树有多少种?dp[i]表示深度为i的个数。sum[i]表示dp的前缀和。转移方程就是:dp[i+1]=dp[i]*sum[i⑴]+dp[i]+dp[i]*(dp[i]⑴)/2;

    然后回到原问题:如果K是偶数(想象中间有个虚拟的不动点),则两边是两棵深度为K/2的2叉树,答案为:dp[i]*(dp[i]⑴)/2+dp[i]

    如果K为奇数,则中间还有1个节点:他也是颗2叉树,则分两种大情况:

                                   第3个2叉树的深度小于K/2,则sum[K/2⑴]*(dp[K/2]*(dp[K/2]⑴)/2+dp[K/2])便可;

                                   第3个2叉树的深度等于K/2,则分3类讨论:1 3棵2叉树结构1样dp[K/2] 2 两棵1样,2 另外一棵不1样:dp[K/2]*(dp[K/2]⑴) 3 3棵都不1样:dp[K/2]*(dp[K/2]⑴)*(dp[K/2]⑵)/6


    代码:

    /******************************************************
    * @author:xiefubao
    *******************************************************/
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #include <cmath>
    #include <map>
    #include <set>
    #include <stack>
    #include <string.h>
    //freopen ("in.txt" , "r" , stdin);
    using namespace std;

    #define eps 1e⑻
    #define zero(_) (abs(_)<=eps)
    const double pi=acos(⑴.0);
    typedef long long LL;
    const int Max=100010;
    const LL INF=1000000007;
    LL ans[Max];
    LL sum[Max];
    LL powa(LL t,LL p)
    {
    LL ans=1;
    while(p)
    {
    if(p&1)
    ans=(ans*t)%INF;
    t=(t*t)%INF;
    p>>=1;
    }
    return ans;
    }
    LL getreverse(LL t)
    {
    return powa(t,INF⑵)%INF;
    }
    LL getans(int t)
    {
    int l=t/2;
    LL rem=((ans[l]*((ans[l]⑴+INF)%INF)%INF*getreverse((LL)2))%INF+ans[l])%INF;
    //cout<<ans[l]<<" "<<rem<<endl;
    if(t&1)
    {
    rem=(rem*sum[l⑴])%INF;
    rem=(rem+ans[l])%INF;
    rem=(rem+ans[l]*(ans[l]⑴)%INF)%INF;
    rem=(rem+ans[l]*((ans[l]⑴+INF)%INF)%INF*((ans[l]⑵+INF)%INF)%INF*getreverse(6)%INF)%INF;
    return rem;
    }
    else
    {
    return rem;
    }
    }
    LL geter(int t)
    {
    return (ans[t⑴]*sum[t⑵]%INF+ans[t⑴]*((ans[t⑴]⑴+INF)%INF)%INF*getreverse(2)%INF+ans[t⑴])%INF;
    }
    void init()
    {
    ans[0]=1;
    ans[1]=1;
    ans[2]=2;
    sum[0]=1;
    sum[1]=2;
    sum[2]=4;

    for(int i=3; i<Max; i++)
    {
    ans[i]=geter(i);
    sum[i]=(sum[i⑴]+ans[i])%INF;
    }

    }
    int main()
    {
    init();
    int n;
    while(cin>>n&&n)
    {
    cout<<getans(n)<<endl;
    }
    return 0;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » hdu 5136(dp计数)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级