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

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條評論
主站蜘蛛池模板: 午夜成人在线视频 | 亚洲一区二区精品视频 | 欧美久久精品一级c片片 | 人人模人人干 | 在线a网站| 黄色在线观看网站 | 久久精品免费在线观看 | 国产亚洲欧美日韩在线看片 | 亚洲午夜日韩高清一区 | 亚洲成人在线观看视频 | 国产精品一区二区不卡 | 久操免费视频 | 久久精品这里热有精品 | 亚洲欧美日韩中文v在线 | 国产精品无码久久av | 国产精品久久久久久久久99热 | 午夜伊人 | 日本在线色 | 日日操干 | 香蕉免费一级视频在线观看 | 欧美一级欧美三级 | 精品欧美一区二区在线看片 | 欧美激情在线观看一区二区三区 | 国产精品久久久久久网站 | 午夜精品福利视频 | 国产精品亚洲专一区二区三区 | 四虎国产精品免费五月天 | 一级毛片特黄久久免费看 | 国产中文在线 | 日本欧美一区二区三区在线 | 91精品国产高清久久久久 | 美女视频久久 | 久久一本一区二区三区 | 亚洲一区视频在线 | www亚洲成人| 久久亚洲精品中文字幕三区 | 国产成人久久综合热 | 五月天婷婷缴情五月免费观看 | 综合久| 精品国精品国产自在久国产应用 | 国产精品美女久久久久网 |