亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

bzoj 1089 SCOI2003嚴格n元樹 遞推

系統 2057 0

挺好想的,就是一直沒調過,我也不知道哪兒的錯,對拍也拍了,因為數據范圍小,都快手動對拍了也不知道

哪兒錯了。。。。

我們定義w[i]代表深度<=i的嚴格n元樹的個數

那么最后w[d]-w[d-1]就是答案

那么對于w[i],我們由w[i-1]遞推來,

我們考慮新加一個根節點,然后根節點有n個子節點,每個子節點都可以建一顆深度<=i-1的樹,那么每個

子節點都有w[i-1]種選法,那么n個子節點就有w[i-1]^n選法,再加上都不選,就是深度為0的情況

那么w[i]:=(w[i-1]^n)+1;

      //
      
        By BLADEVIL


      
      
        var
      
      
        

    w                           :
      
      
        array
      
      [-
      
        1
      
      ..
      
        100
      
      ] 
      
        of
      
      
         ansistring;

    n, d                        :longint;

    a, b, c                     :
      
      
        array
      
      [
      
        0
      
      ..
      
        100000
      
      ] 
      
        of
      
      
         int64;

 


      
      
        function
      
      
         mul(s1,s2:ansistring):ansistring;


      
      
        var
      
      
        

    i, j                        :longint;

    len1, len2                  :longint;

    s                           :ansistring;


      
      
        begin
      
      
        

    len1:
      
      =
      
        length(s1);

    len2:
      
      =
      
        length(s2);

    fillchar(c,sizeof(c),
      
      
        0
      
      
        );

    fillchar(a,sizeof(a),
      
      
        0
      
      
        );

    fillchar(b,sizeof(b),
      
      
        0
      
      
        );

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len1 
      
        do
      
       a[(len1-i) 
      
        div
      
      
        4
      
      +
      
        1
      
      ]:=a[(len1-i) 
      
        div
      
      
        4
      
      +
      
        1
      
      ]*
      
        10
      
      +ord(s1[i])-
      
        48
      
      
        ;

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len2 
      
        do
      
       b[(len2-i) 
      
        div
      
      
        4
      
      +
      
        1
      
      ]:=b[(len2-i) 
      
        div
      
      
        4
      
      +
      
        1
      
      ]*
      
        10
      
      +ord(s2[i])-
      
        48
      
      
        ;

    len1:
      
      =(len1+
      
        3
      
      ) 
      
        div
      
      
        4
      
      
        ;

    len2:
      
      =(len2+
      
        3
      
      ) 
      
        div
      
      
        4
      
      
        ;

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len1 
      
        do
      
      
        for
      
       j:=
      
        1
      
      
        to
      
       len2 
      
        do
      
      
        begin
      
      
        

            c[i
      
      +j-
      
        1
      
      ]:=c[i+j-
      
        1
      
      ]+a[i]*
      
        b[j];

            c[i
      
      +j]:=c[i+j]+c[i+j-
      
        1
      
      ] 
      
        div
      
      
        10000
      
      
        ;

            c[i
      
      +j-
      
        1
      
      ]:=c[i+j-
      
        1
      
      ] 
      
        mod
      
      
        10000
      
      
        ;

        
      
      
        end
      
      
        ;

    mul:
      
      =
      
        ''
      
      
        ;

    len1:
      
      =len1+len2+
      
        1
      
      
        ;

    
      
      
        for
      
       i:=len1 
      
        downto
      
      
        1
      
      
        do
      
      
        begin
      
      
        if
      
       c[i]<
      
        1000
      
      
        then
      
       mul:=mul+
      
        '
      
      
        0
      
      
        '
      
      
        ;

        
      
      
        if
      
       c[i]<
      
        100
      
      
        then
      
       mul:=mul+
      
        '
      
      
        0
      
      
        '
      
      
        ;

        
      
      
        if
      
       c[i]<
      
        10
      
      
        then
      
       mul:=mul+
      
        '
      
      
        0
      
      
        '
      
      
        ;

        str(c[i],s);

        mul:
      
      =mul+
      
        s;

    
      
      
        end
      
      
        ;

    
      
      
        while
      
       (mul[
      
        1
      
      ]=
      
        '
      
      
        0
      
      
        '
      
      ) 
      
        and
      
       (length(mul)>
      
        1
      
      ) 
      
        do
      
       delete(mul,
      
        1
      
      ,
      
        1
      
      
        );


      
      
        end
      
      
        ;

 


      
      
        function
      
      
         mi(x:ansistring):ansistring;


      
      
        var
      
      
        

    p                           :longint;

    ans, sum                    :ansistring;


      
      
        begin
      
      
        

    ans:
      
      =
      
        '
      
      
        1
      
      
        '
      
      
        ;

    sum:
      
      =
      
        x;

    p:
      
      =
      
        n;

    
      
      
        while
      
       p<>
      
        0
      
      
        do
      
      
        begin
      
      
        if
      
       p 
      
        mod
      
      
        2
      
      =
      
        1
      
      
        then
      
       ans:=
      
        mul(ans,sum);

        p:
      
      =p 
      
        div
      
      
        2
      
      
        ;

        sum:
      
      =
      
        mul(sum,sum);

    
      
      
        end
      
      
        ;

    mi:
      
      =
      
        ans;


      
      
        end
      
      
        ;

     


      
      
        function
      
      
         inc(x:ansistring):ansistring;


      
      
        var
      
      
        

    len                         :longint;

    i                           :longint;

    s                           :ansistring;

     


      
      
        begin
      
      
        

    len:
      
      =
      
        length(x);

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len 
      
        do
      
       c[i]:=ord(x[i])-
      
        48
      
      
        ;

    c[len]:
      
      =c[len]+
      
        1
      
      
        ;

    
      
      
        for
      
       i:=len 
      
        downto
      
      
        1
      
      
        do
      
      
        begin
      
      
        

        c[i
      
      -
      
        1
      
      ]:=c[i-
      
        1
      
      ]+c[i] 
      
        div
      
      
        10
      
      
        ;

        c[i]:
      
      =c[i] 
      
        mod
      
      
        10
      
      
        ;

    
      
      
        end
      
      
        ;

    inc:
      
      =
      
        ''
      
      
        ;

    len:
      
      =
      
        len;

    
      
      
        for
      
       i:=
      
        0
      
      
        to
      
       len 
      
        do
      
      
        begin
      
      
        

        str(c[i],s);

        inc:
      
      =inc+
      
        s;

    
      
      
        end
      
      
        ;

    
      
      
        while
      
       (inc[
      
        1
      
      ]=
      
        '
      
      
        0
      
      
        '
      
      ) 
      
        and
      
       (length(inc)>
      
        1
      
      ) 
      
        do
      
       delete(inc,
      
        1
      
      ,
      
        1
      
      
        );


      
      
        end
      
      
        ;

     


      
      
        function
      
      
         jian(s1,s2:ansistring):ansistring;


      
      
        var
      
      
        

    i                           :longint;

    len1, len2                  :longint;

    s                           :ansistring;


      
      
        begin
      
      
        

    len1:
      
      =
      
        length(s1);

    len2:
      
      =
      
        length(s2);

    fillchar(c,sizeof(c),
      
      
        0
      
      
        );

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len1 
      
        do
      
       a[len1-i+
      
        1
      
      ]:=ord(s1[i])-
      
        48
      
      
        ;

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len2 
      
        do
      
       b[len2-i+
      
        1
      
      ]:=ord(s2[i])-
      
        48
      
      
        ;

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len1 
      
        do
      
       c[i]:=a[i]-
      
        b[i];

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       len1 
      
        do
      
      
        if
      
       c[i]<
      
        0
      
      
        then
      
      
        begin
      
      
        

            c[i]:
      
      =c[i]+
      
        10
      
      
        ;

            c[i
      
      +
      
        1
      
      ]:=c[i+
      
        1
      
      ]-
      
        1
      
      
        ;

        
      
      
        end
      
      
        ;

    jian:
      
      =
      
        ''
      
      
        ;

    
      
      
        for
      
       i:=len1 
      
        downto
      
      
        1
      
      
        do
      
      
        begin
      
      
        

        str(c[i],s);

        jian:
      
      =jian+
      
        s;

    
      
      
        end
      
      
        ;

    
      
      
        while
      
       (jian[
      
        1
      
      ]=
      
        '
      
      
        0
      
      
        '
      
      ) 
      
        and
      
       (length(jian)>
      
        1
      
      ) 
      
        do
      
       delete(jian,
      
        1
      
      ,
      
        1
      
      
        );


      
      
        end
      
      
        ;

     


      
      
        procedure
      
      
         main;


      
      
        var
      
      
        

    i                           :longint;


      
      
        begin
      
      
        

    readln(n,d);

    
      
      
        if
      
       d=
      
        0
      
      
        then
      
      
        begin
      
      
        

        writeln(
      
      
        1
      
      
        );

        exit;

    
      
      
        end
      
      
        ;

    w[
      
      
        0
      
      ]:=
      
        '
      
      
        1
      
      
        '
      
      
        ;

    
      
      
        for
      
       i:=
      
        1
      
      
        to
      
       d 
      
        do
      
       w[i]:=inc(mi(w[i-
      
        1
      
      
        ]));

    writeln(jian(w[d],w[d
      
      -
      
        1
      
      
        ]));


      
      
        end
      
      
        ;

    


      
      
        begin
      
      
        

    main;


      
      
        end
      
      .
    

?

bzoj 1089 SCOI2003嚴格n元樹 遞推


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产综合日韩伦理 | 久久四虎 | 久操视频在线播放 | 久久机热这里只有精品无需 | 亚洲欧美一区二区视频 | 亚洲va久久久久综合 | 中文字幕免费观看视频 | 欧美video巨大粗暴18 | 天天干天天操天天摸 | 欧美日韩一区二区三在线 | 这里只有精品在线观看 | 狠狠狠操 | 97dyy在线观看手机版 | 亚洲成a人在线播放www | 国产视频一区二 | 男人的天堂久久精品激情 | 亚洲一区欧洲一区 | 欧美啊v在线观看 | 久草在线国产视频 | 色爱区综合| 98色花堂国产精品首页 | 伊人伊色| 精品国产一区二区三区久 | 毛片成人永久免费视频 | 久久这里只有精品久久 | 亚洲综合激情另类图片专区 | 欧美国产日产精品免费视频 | 成人欧美一区在线视频在线观看 | 91国内精品久久久久影院优播 | 国产成人高清亚洲一区久久 | 免费在线观看亚洲 | 在线看的毛片 | 新四虎影院 | 日本特黄a级高清免费大片18 | 夜夜爽66| 国产日韩成人 | 一级无毛片 | 色综合综合色 | 九九99热久久精品在线9 | 毛片大全高清免费 | 国产精品午夜久久久久久99热 |