链接：Link 耗时：0.679s

分析

本质上，这是一道求数列通项的题目。我们列出前几个字符串： $$01,$$ $$1001,$$ $$01101001,$$ $$1001011001101001,$$ $$\ldots$$

如果用$S_i$表示第i个字符串中“00”的个数，则有： $$S_1=0,\ S_2=1,\ S_3=1,\ S_4=3,\ S_5=5,\ S_6=11,\ldots$$

经过观察可以发现有如下规律： $$S_n=2\times S_{n-1}+{(-1)}^n$$

求通项就简单了，换个元即可： $$S_n=\frac{1}{3}[{(-1)}^n+2^{n-1}]$$

程序采用高精度实现。

Code

const    JINDU = 100000;var    n: Integer;//在数字前补0procedure PrintANumber(x: longint);var    t: longint;begin    if x = 0 then        write('00000')    else    begin        t := JINDU;        while t > x * 10 do        begin            write(0);            t := t div 10;        end;        write(x);    end;end;var    ans: array [1..300] of longint;    len, i: integer;//计算2^(n-1)procedure calc2;var    i, x, t, mul: longint;begin    len := 1;    ans[1] := 1;    t := n-1;    while t > 0 do    begin        if t < 6 then            mul := 1 << t        else            mul := 64;        x := 0;        for i := 1 to len do        begin            ans[i] := ans[i] * mul + x;            x := ans[i] div JINDU;            ans[i] := ans[i] mod JINDU;        end;        if x > 0 then        begin            inc(len);            ans[len] := x;        end;        dec(t, 6);    end;end;//除以3procedure div3;var    i, x, t: longint;begin    i := len;    x := 0;    while i > 0 do    begin        t := (x * JINDU + ans[i]);        ans[i] := t div 3;        x := t mod 3;        dec(i);    end;    while ans[len] = 0 do dec(len);end;begin    assign(input, 'main.in'); reset(input);    assign(output, 'main.out'); rewrite(output);    while not eof do    begin        readln(n);        if n=1 then   //特殊情况处理        begin            writeln(0);            continue;        end;        fillchar(ans, sizeof(ans), 0);        calc2;        if odd(n) then            dec(ans[1])        else            inc(ans[1]);        div3;        write(ans[len]);        for i := len-1 downto 1 do            PrintANumber(ans[i]);        writeln;    end;    close(input); close(output);end.