/ Vijos / 题库 / 二叉树数 /

题解

59 条题解

  • 0
    @ 2019-07-24 15:35:33

    #include<bits/stdc++.h>
    using namespace std;
    const int Max_n=5005;

    int n,a[Max_n<<2],len;
    inline void Multiply(int n)
    {
    for(int i=1;i<=len;++i)
    a[i]*=n;
    for(int i=1;i<len;++i)
    {
    a[i+1]+=(a[i]/10);
    a[i]%=10;
    }
    while(a[len]>10)
    {
    a[len+1]+=(a[len]/10);
    a[len]%=10;
    len++;
    }
    }
    inline void chu(int n)
    {
    for(int i=len;i;i--)
    {
    a[i-1]+=(10*(a[i]%n));
    a[i]/=n;
    }
    while(!a[len])
    len--;
    }
    int main()
    {
    cin>>n;
    memset(a,0,sizeof(a));
    len=1;
    a[1]=1;
    for(int i=n+2;i<=2*n;++i)
    Multiply(i);
    for(int i=2;i<=n;++i)
    chu(i);
    for(int i=len;i;--i)
    cout<<a[i];
    return 0;
    }

  • 0
    @ 2016-05-22 09:56:45

    type tt=array [0..50005] of longint;
    var
    a,b,c:tt;
    k,p,n,m,i,l1,l2,l3:longint;
    procedure cch;
    var i,j,x:longint;
    begin
    fillchar(c,sizeof(c),0);
    for i:=1 to l1 do
    begin
    x:=0;
    for j:=1 to l2 do
    begin
    x:=x+a[i]*b[j]+c[i+j-1];
    c[i+j-1]:=x mod 10000;
    x:=x div 10000;
    end;
    c[i+l2]:=x;
    end;
    if (c[l1+l2]<>10000) then l3:=l1+l2 else l3:=l1+l2-1;
    end;
    procedure jy(t:longint);
    var i,x:longint;
    begin
    fillchar(b,sizeof(b),0);
    x:=0;
    for i:=l1 downto 1 do
    begin
    x:=x*10000+a[i];
    b[i]:=x div t;
    x:=x mod t;
    end;
    l2:=l1;
    while (b[l2]=0) and (l2>1) do dec(l2);
    end;
    procedure fj(x:longint);
    var i:longint;
    begin
    fillchar(b,sizeof(b),0);
    i:=0;
    while (x<>0) do
    begin inc(i); b[i]:=x mod 10000; x:=x div 10000; end;
    l2:=i;
    end;
    procedure jzq(a:tt; l:longint);
    var i:longint;
    begin
    write(a[l]);
    for i:=l-1 downto 1 do
    if (a[i]>999) then write(a[i])
    else if (a[i]>99) then write(0,a[i])
    else if (a[i]>9) then write('00',a[i])
    else write('000',a[i]);
    end;
    begin
    read(n);
    a[1]:=1; l1:=1;
    for i:=n+2 to n*2 do
    begin fj(i); cch; l1:=l3; a:=c; end;
    for i:=2 to n do
    begin jy(i); a:=b; l1:=l2; end;
    jzq(a,l1);
    end.

  • 0
    @ 2015-08-08 11:45:58

    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int MAXN = 10000000;

    long int s[MAXN], len = 1;

    int cheng(int x, int l){
    for(int i=0; i<l; i++)
    s[i] *= x;
    for(int i=0; i<=l; i++){
    s[i+1] += s[i] / 10000;
    s[i] %= 10000;

    }
    for(int i=l+3; ; i--)
    if(s[i] != 0){
    l = i+1;
    break;
    }
    return l;
    }

    int chu(int x, int l){
    int flag = 0;
    for(int i=l-1; i>=0; i--){
    while(s[i] < x){
    s[i-1] += s[i]*10000;
    s[i] = 0;
    i--;
    if(i<0)
    flag = 1;
    }
    if(flag) break;
    s[i-1] += s[i] % x * 10000;
    s[i] /= x;
    }
    for(int i=l-1; i>=0; i--)
    if(s[i] != 0){
    l = i+1;
    break;
    }
    return l;
    }

    int main()
    {
    int n;
    scanf("%d", &n);
    s[0] = 1;

    for(int i=1; i<=n; i++){
    len = cheng(4*i-2, len);
    len = chu(i+1, len);
    }
    printf("%d",s[len-1]);
    for(int i=len-2; i>=0; i--){
    if(s[i] >= 1000)
    printf("%d",s[i]);
    else if(s[i] >= 100) printf("0%d",s[i]);
    else if(s[i] >= 10) printf("00%d",s[i]);
    else printf("000%d",s[i]);

    }
    return 0;
    }
    catalan + 高精 +压位

  • 0
    @ 2014-08-02 16:37:00

    原本想展现一下自己收集的各种高大上的高精度板子的。。。结果各种蛋疼还不想手写，干脆上Java。。。高精度的必杀技

    Block code

    import java.util.Scanner;
    import java.math.BigInteger;
    import java.lang.String;
    public class Main {
    static public void main(String args[])
    {
    int n,i;
    Scanner in=new Scanner(System.in);
    n=in.nextInt();
    BigInteger a=new BigInteger("1");
    for (i=1;i<=n;i++)
    {
    String b=String.valueOf(4*i-2);

    String c=String.valueOf(i+1);

    BigInteger d=new BigInteger(b);

    BigInteger e=new BigInteger(c);

    a=a.multiply(d);
    a=a.divide(e);

    }
    System.out.println(a);
    in.close();
    }
    }

  • 0
    @ 2014-01-01 12:01:35

    Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2013-11-07 23:20:57

    90分
    program p1388;
    type arr=array[0..5000] of longint;
    var a:array[0..5000] of arr; n:longint;
    //
    procedure init;
    var i:longint;
    begin
    assign(input,'p1388.in');assign(output,'p1388.out');
    reset(input);rewrite(output);
    read(n);
    end;
    //
    procedure cheng(a,b:arr;var c:arr);
    var i,j:longint;
    begin
    fillchar(c,sizeof(c),0);
    for i:=1 to a[0] do
    for j:=1 to b[0] do c[i+j-1]:=c[i+j-1]+a[i]*b[j];
    for i:=1 to a[0]+b[0]-1 do
    begin
    c[i+1]:=c[i+1]+(c[i] div 10);
    c[i]:=c[i] mod 10;
    end;
    c[0]:=a[0]+b[0];
    while c[c[0]]=0 do dec(c[0]);
    end;
    //
    procedure jia(a:arr;var b:arr);
    var i,j:longint;
    begin
    if a[0]>b[0] then j:=a[0]
    else j:=b[0];
    for i:=1 to j do
    begin
    b[i]:=a[i]+b[i];
    end;
    for i:=1 to j do
    begin
    b[i+1]:=b[i+1]+(b[i] div 10);
    b[i]:=b[i] mod 10;
    end;
    if b[j+1]<>0 then b[0]:=j+1
    else b[0]:=j;
    end;
    //
    procedure main;
    var i,j,k:longint;
    c:arr;
    begin
    a[0,0]:=1;a[0,1]:=1;
    a[1,0]:=1;a[1,1]:=1;
    for i:=2 to n do
    begin
    for j:=0 to i-1 do
    begin
    cheng(a[j],a[i-j-1],c); jia(c,a[i]);
    end;
    end;
    for j:=a[i,0] downto 1 do
    begin
    write(a[i,j]);
    end;
    close(output);
    end;
    //
    begin
    init;
    main;
    end.

  • 0
    @ 2013-10-30 19:27:35

    测试数据 #0: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    Accepted, time = 0 ms, mem = 920 KiB, score = 100
    const
    o=10000;
    var
    i,j,k,x,n,n1,top:longint;
    l,t:int64;
    s:string;
    su:array[0..10000]of boolean;
    ans:array[0..2000]of longint;
    su_table,number:array[0..10000]of longint;

    procedure findsu;
    var x:longint;
    begin
    su_table[1]:=2;
    t:=1;
    for i:=0 to n do if(not su[i])then
    begin
    inc(t);
    su_table[t]:=2*i+3;
    x:=(2*i*i+6*i+3);
    while(x<=n1)do
    begin
    su[x]:=true;
    inc(x,su_table[t]);
    end;
    end;
    end;

    procedure num;
    begin
    for i:=1 to t do
    begin
    l:=su_table[i];
    while(l<=n1)do
    begin
    inc(number[i],n1 div l);
    dec(number[i],n div l);
    dec(number[i],(n+1) div l);
    l:=l*su_table[i];
    end;
    end;
    end;

    begin
    read(n);
    n1:=n<<1;
    findsu; num;
    ans[1]:=1; top:=1;
    for i:=1 to t do
    for j:=1 to number[i] do
    begin
    x:=0;
    for k:=1 to top do
    begin
    ans[k]:=ans[k]*su_table[i]+x;
    x:=ans[k] div o;
    ans[k]:=ans[k] mod o;
    end;
    while(x>0)do
    begin
    inc(top);
    ans[top]:=x mod o;
    x:=x div o;
    end;
    end;
    write(ans[top]);
    for i:=top-1 downto 1 do
    begin
    str(ans[i],s);
    while(length(s)<4)do s:='0'+s;
    write(s);
    end;
    end.

    • @ 2013-10-30 19:29:49

      嘻嘻，，，，，，，，好，顶一个！

  • 0
    @ 2013-10-30 19:27:22

    测试数据 #0: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 916 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 920 KiB, score = 10
    Accepted, time = 0 ms, mem = 920 KiB, score = 100
    const
    o=10000;
    var
    i,j,k,x,n,n1,top:longint;
    l,t:int64;
    s:string;
    su:array[0..10000]of boolean;
    ans:array[0..2000]of longint;
    su_table,number:array[0..10000]of longint;

    procedure findsu;
    var x:longint;
    begin
    su_table[1]:=2;
    t:=1;
    for i:=0 to n do if(not su[i])then
    begin
    inc(t);
    su_table[t]:=2*i+3;
    x:=(2*i*i+6*i+3);
    while(x<=n1)do
    begin
    su[x]:=true;
    inc(x,su_table[t]);
    end;
    end;
    end;

    procedure num;
    begin
    for i:=1 to t do
    begin
    l:=su_table[i];
    while(l<=n1)do
    begin
    inc(number[i],n1 div l);
    dec(number[i],n div l);
    dec(number[i],(n+1) div l);
    l:=l*su_table[i];
    end;
    end;
    end;

    begin
    read(n);
    n1:=n<<1;
    findsu; num;
    ans[1]:=1; top:=1;
    for i:=1 to t do
    for j:=1 to number[i] do
    begin
    x:=0;
    for k:=1 to top do
    begin
    ans[k]:=ans[k]*su_table[i]+x;
    x:=ans[k] div o;
    ans[k]:=ans[k] mod o;
    end;
    while(x>0)do
    begin
    inc(top);
    ans[top]:=x mod o;
    x:=x div o;
    end;
    end;
    write(ans[top]);
    for i:=top-1 downto 1 do
    begin
    str(ans[i],s);
    while(length(s)<4)do s:='0'+s;
    write(s);
    end;
    end.

  • 0
    @ 2009-11-01 21:32:36

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 384ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：384ms

    分解质因数，卡特兰数，注意压位高精

  • 0
    @ 2009-10-29 17:21:27

    其实....分解质因数然后直接卡特兰公式才是王道- -|||

  • 0
    @ 2009-10-24 20:31:13

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 447ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：447ms

    烂程序。。懒得贴了。。

  • 0
    @ 2009-10-11 10:45:56

    太悲哀了，竟然把n

  • 0
    @ 2009-10-06 16:48:22

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    我再次无语了

    本来想用这个连连高精除

    结果通过率就下去了

  • 0
    @ 2009-09-26 14:10:41

    终于 A 了

    边乘边除

    数组大点就能过

  • 0
    @ 2009-09-24 12:54:20

    纯数学公式+高精~~~

  • 0
    @ 2009-09-23 18:36:23

    AC

    catalan数

    C(2n,n)/(n-1)

    高精度

  • 0
    @ 2009-08-07 11:16:41

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    1.素数表要开到1000的范围

    2.万进制的话数组要开到800

  • 0
    @ 2009-07-08 01:32:44

    高精度Catalan

  • 0
    @ 2009-05-15 17:06:56

    素数表，好东西啊，Vijos有五道题都可以用素数表做。

  • 0
    @ 2009-05-08 17:41:37

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    轻松秒杀！

    思路：c(2n,n)/(n+1)

    统计最后结果的每个质因数个数，直接相乘。

    附程序：

    var

    c,x,y:array[0..10000] of longint;

    i,j,k,n,p,q:longint;

    s:string;

    begin

    read(n);

    for i:=n+1 to 2*n do

    begin

    k:=i;

    for j:=2 to i do

    begin

    while not(k mod j0) do

    begin

    inc(y[j]);

    k:=k div j;

    end;

    if k=1 then break;

    end;

    end;

    for i:=2 to n+1 do

    begin

    k:=i;

    for j:=2 to i do

    begin

    while not(k mod j0) do

    begin

    dec(y[j]);

    k:=k div j;

    end;

    if k=1 then break;

    end;

    end;

    c[1]:=1;

    c[0]:=1;

    for p:=2 to 2*n do

    if y[p]>0 then

    for i:=1 to y[p] do

    begin

    for j:=1 to c[0] do

    c[j]:=c[j]*p;

    str(p,s);

    for j:=1 to c[0]+length(s) do

    begin

    c[j+1]:=c[j+1]+c[j] div 100000;

    c[j]:=c[j] mod 100000;

    end;

    for j:=c[0]+length(s) downto c[0] do

    if c[j]0 then

    begin

    c[0]:=j;

    break;

    end;

    end;

    write(c[c[0]]);

    for i:=c[0]-1 downto 1 do

    if c[i]>10000 then write(c[i])

    else if c[i]>1000 then write(0,c[i])

    else if c[i]>100 then write('00',c[i])

    else if c[i]>10 then write('000',c[i])

    else write('0000',c[i]);

    end.

二叉树数

信息

ID
1388
难度
6
分类
组合数学 | Catalan数列 点击显示
标签
(无)
递交数
1178
已通过
302
通过率
26%
被复制
2
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1