挺好想的,就是一直沒調過,我也不知道哪兒的錯,對拍也拍了,因為數據范圍小,都快手動對拍了也不知道
哪兒錯了。。。。
我們定義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 .
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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