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

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條評論
主站蜘蛛池模板: 欧美国产一区二区二区 | 久久久久久久久综合 | 免费国产一级特黄aa大片在线 | 免费女人18毛片a级毛片视频 | 国产成+人+亚洲+欧美综合 | 五月天丁香六月欧美综合 | 四虎4hu永久免费视频大全 | 手机看片神马午夜片 | 亚洲国产精品久久久久久 | 天上人间影院久久国产 | 国产99欧美精品久久精品久久 | 337p日本大胆欧美人术艺术6 | 亚洲一区二区三区网站 | 欧美激情 亚洲 | 国产亚洲精品久久yy5099 | 免费一级特黄欧美大片勹久久网 | 国产成人久久精品区一区二区 | 九九热线精品视频6一 | 中文一级国产特级毛片视频 | 久久综合狠狠综合久久综合88 | 欧美日韩色 | 四虎在线永久视频观看 | 一级高清毛片免费a级高清毛片 | 久久久久久久国产a∨ | 久久精品国产一区二区三区日韩 | 欧美又粗又硬 | 欧美亚洲国产精品久久第一页 | 毛片站| 亚洲精品国产精品乱码不卞 | 成年女人18级毛片毛片免费观看 | 亚洲高清在线视频 | 99久久精品免费观看区一 | 四虎永久在线日韩精品观看 | 亚洲一级毛片在线观 | 日日干日日操 | 黄黄视频免费看 | 亚洲综合色视频在线观看 | 欧美xxxwww| 亚洲人xx视频 | 国产成人综合一区精品 | 91久久精品国产一区二区 |