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

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條評論
主站蜘蛛池模板: 日本不卡1| 精品国产亚一区二区三区 | 中文字幕亚洲综合久久菠萝蜜 | 99久久综合国产精品免费 | 成人免费视频在 | 免费一级a毛片夜夜看 | 日韩欧美无线在码 | 亚洲精品久久99久久 | 久久国产精品视频 | 国产成人免费不卡在线观看 | 奇米影视一区二区三区 | 亚洲人成网站色7799在线观看 | 日日夜夜精品免费视频 | 日韩有码第一页 | 3级毛片| 九九久久国产精品 | 亚洲国产品综合人成综合网站 | 精品成人免费播放国产片 | 亚洲综合色就色手机在线观看 | 欧美日韩国产精品综合 | 福利视频免费看 | 91久久视频| 久草在线视频看看 | 99热热久久这里只有精品8 | 亚洲免费在线观看 | 青青热在线精品视频免费 | 最新国产三级久久 | 国产日韩欧美在线观看免费视频 | 成人综合久久精品色婷婷 | 国产日韩91 | 欧美老妇免费做爰视频 | 国产日韩欧美精品在线 | 久青草资源福利视频 | 狠狠色成人综合网图片区 | 欧美日韩福利视频一区二区三区 | 欧美性猛交aa一级 | 中文国产成人精品久久一区 | 天天干天天干 | 日本免费一级 | 亚色在线播放 | 婷婷爱爱 |