sum=[]
sum.append(0)
for i in range(1,1500001):
    sum.append(sum[i-1]+sum[i//2]+1)
if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            k=n//2
            print(sum[k] + 1)
        except EOFError:
            break

#include<bits/stdc++.h>
using namespace std;
const int e=7,mod=100000000;
int f[1500000+1][e+1],n;
void s(int *a,int *b,int *o) {
    for(int i = e;i>=1;i--) {
        o[i] += a[i]+b[i];
        o[i-1] += o[i]/mod;
        o[i] %= mod;
    }
}
void p(int *n) {
    int i,j,l;
    for(i=0; i<=e && n[i]==0; i++);
    
    cout<<n[i];
    for(++i;i<=e;i++){
        l = 1+(int)log10(n[i]);
        for(j=8;j>l;j--)
        putchar('0');
        cout<<n[i];
    } 
    cout<<endl; 
}
int main() 
{
    int n;
    f[0][e]=1;
    
    for(int i = 1;i<=1500000;i++)
    s(f[i-1],f[i/2],f[i]);
    while(cin >> n) 
        p(f[n/2]);
        
    return 0;
}

const py=10000;
type dd=array[0..21] of integer;
var
f:array[0..1500001] of dd;
i,j,n:longint;
begin
f[0][1]:=1; f[0][0]:=1;
for i:=1 to 1500000 do
for j:=1 to 20 do
begin
f[i][j]:=f[i][j]+f[i-1][j]+f[i div 2][j];
f[i][j+1]:=f[i][j+1]+f[i,j] div py;
f[i,j]:=f[i,j] mod py;
end;
while not(eof) do
begin
readln(n);
n:=n shr 1;
for i:=20 downto 1 do
if f[n,i]<>0 then break;
write(f[n,i]);
for j:=i-1 downto 1 do
begin
if f[n,j]<1000 then write('0');
if f[n,j]<100 then write('0');
if f[n,j]<10 then write('0');
write(f[n,j]);
end;
writeln;
end;
end.

烧味场[wuoicu;.'piusa

](http://)

令所求为\(ans\)

朴素解法:

\(ans[0..1]=1\)
\(ans[i] = \sum_{k=1}^{\lfloor \frac i 2 \rfloor} ans[k]\)

差分，如下:

\(ans[i] - ans[i-1] = \left \{ \begin{array}{ll}ans\left[\frac i 2\right] & i\mod 2 == 0 \\0 & i \mod 2 == 1\end{array} \right. \)

移项，如下:

\(ans[i] = ans[i-1] + \left\{\begin{array}{ll} ans\left[\frac i 2\right] & i\mod 2 == 0 \\ 0 & i \mod 2 == 1 \end{array}\right. \)

观察到奇偶项存在相同部分，以2差分:

\(ans\left[i\right] = ans\left[i-2\right] + ans\left[\left\lfloor \frac i 2\right\rfloor\right]\)

则对\(\left\lfloor\frac i 2\right\rfloor\),有:

\(ans\left[\left\lfloor\frac i 2\right\rfloor\right] = ans\left[\left\lfloor\frac{i-1} 2\right\rfloor\right] +ans\left[\left\lfloor \frac {\left\lfloor \frac i 2\right\rfloor} 2\right\rfloor\right]\)

令\(dp[i] = ans\left[\left\lfloor\frac i 2\right\rfloor\right]\)
则:\(dp[i] = dp\left[i-1\right]+dp\left[\left\lfloor \frac i 2 \right\rfloor\right]\)

import Data.Array

dp::Array Int Integer
dp = array (0,1500000) $ (0,1) : [(i,ans i) | i<-[1..1500000]]
    where ans i = dp!(i-1) + dp!(i`div`2)

solve::Int->Integer
solve n = dp!(n`div`2)

main::IO()
main = interact $ unlines.map (show.solve.read).words

//f(n)=f(n-2)+f(n/2)-----n%2==0
//f(n)=f(n-1)------------n%2==1
//先计算1--300W保存，然后直接取出来；
//当然这里可以优化，只保存1-150W ，最后输出的时候再运算一次也可以
//题目对于输入输出描述的不是很清楚
//输入包含若干组数据……一开始以为只有一组23333，因此要使用while(scanf()!=EOF)
//输出是一个测试数据对应了一行输出
#include<cstdio>
#include<cstring>
const unsigned int N=1E+9;//满10^9进位
unsigned int brr[3000001][6];//6位int来表示长度为50的足够了
int main(){
memset(brr,0,sizeof(brr));
brr[1][0]=1;//f(1)=1
brr[2][0]=2;//f(2)=2
int m=3000000;

for(int i=3;i<=m;i++){
if(i%2==1){//f(n)=f(n-1)---------n%2==1
for(int j=0;j<6;j++)
brr[i][j]=brr[i-1][j];
}
//arr[i]=arr[i-1];
else{//f(n)=f(n-2)+f(n/2)-------n%2==0
for(int j=0;j<6;j++){
//j越大表示数字位（类似个十百千）越高
brr[i][j]+=brr[i-2][j]+brr[i/2][j];
if(brr[i][j]>=N){
brr[i][j]%=N;
brr[i][j+1]++;
}
}
}
}
int n;
while(scanf("%d",&n)!=EOF){//前面已经计算完了，这里直接取出来输出
int flag=0;
for(int j=5;j>=0;j--){
if(flag)//如果之前已经输出过有效数字那么当前的9位数字都要输出
printf("%09d",brr[n][j]);
else{
if(brr[n][j]){
printf("%d",brr[n][j]);
flag=1;
}
}

}
printf("\n");

}
return 0;
}

const oo=1000000000000000000;
var n,i:longint;
j:byte;
a:array[0..3000000,0..4] of qword;
st:string[20];
procedure adding;
begin
a[i,0]:=a[i-1,0];
for j:=1 to a[i,0] do
begin
a[i,j]:=a[i,j]+a[i-1,j]+a[i div 2,j];
a[i,j+1]:=a[i,j] div oo;
a[i,j]:=a[i,j] mod oo;
end;
if a[i,a[i,0]+1]>0 then inc(a[i,0]);
end;
begin
a[0,0]:=1;
a[0,1]:=1;
for i:=1 to 3000000 do
if i mod 2=1 then a[i]:=a[i-1]
else adding;
while not eof do
begin
readln(n);
write(a[n,a[n,0]]);
for i:=a[n,0]-1 downto 1 do
begin
str(a[n,i],st);
while length(st)<18 do st:='0'+st;
write(st);
end;
writeln;
end;
end.
竟然要记忆化！
超了两次！

#include <stdio.h>
#include <string.h>
#include <math.h>
#define END 7
#define MOD 100000000
int f[1500001][END+1];
void plus(int *a, int *b, int *out){
int i;
for(i=END; i>=1; i--){
out[i] += a[i]+b[i];
out[i-1] += out[i]/MOD;
out[i] %= MOD;
}
}
void print(int *num){
int i, j, length;
for(i=0; i<=END && num[i]==0; i++)
;
printf("%d", num[i]);
for(++i; i<=END; i++){
length = 1 + (int)log10(num[i]);
for(j=8; j>length; j--)
putchar('0');
printf("%d", num[i]);
}
putchar('\n');
}
int main(){
int n, i;
memset(f, 0, sizeof(f));
f[0][END] = 1;
for(i=1; i<=1500000; i++)
plus(f[i-1], f[i/2], f[i]);
while(scanf("%d", &n) != EOF)
print(f[n/2]);
return 0;
}

C语言，递推，高精度压成了十位数。
首先发现一个规律 F[n]=∑F[1...n/2]+1
写几个出来
F[2]=F[3]=F[1]+1
F[4]=F[5]=F[1..2]+1=F[1]+1+F[2]=2F[2]
F[6]=F[7]=F[1..3]+1=F[1..2]+1+F[3]=F[4]+F[3]
F[7]=F[8]=F[1..4]+1=F[1..3]+1+F[4]=F[6]+F[4]
规律就是
F[n]=F[n+1]=F[n-1]+Fn/2
F[n-1]=F[n] =F[n-2]+Fn/2
干脆一开始n=n/2;==> 答案为 F[n]=F[n-1]+F[n/2];
~~~~~~~~~~~~~~~~~~~~~~~~~(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)~~~~~~~~~~~~~~~~~~~~~~~~~
测试数据 #0: Accepted, time = 0 ms, mem = 41532 KiB, score = 10
测试数据 #1: Accepted, time = 140 ms, mem = 41536 KiB, score = 30
测试数据 #2: Accepted, time = 171 ms, mem = 41536 KiB, score = 60

#include<stdio.h>
#define P 1000000000//10位
int n,i,j,k,len=1;
int F[1500001][7];
void jia(int a[],int b[],int c[])
{
int i;
for(i=0;i<len;i++) { c[i]+=a[i]+b[i];if(c[i]>=P) {c[i]-=P;c[i+1]++;} }
if(c[len]!=0) len++;
}
void output(void)
{
int i,j,k;
for(i=6;F[n][i]==0;i--) ;
printf("%d",F[n][i--]);//输出最高位
for(;i>=0;i--)
{
for(j=1,k=0 ;F[n][i]/j; j*=10,k++);//k位

for(;k<9;k++)printf("0"); printf("%d",F[n][i]);//不足9位的输出0

} printf("\n");
}
int main(void)
{
int m=0;
while(scanf("%d",&n)==1)
{

if(n==0){printf("0\n");continue;}//特判
n/=2; F[0][0]=1;
for(i=m+1;i<=n;i++) jia(F[i-1],F[i/2],F[i]);
if(m<n)m=n;//记录算过的最大n，下次不再算
output();
}
return 0;

}

写高精度即可

“包含多组测试数据”坑到我了........

先把0到150W的答案全算好....
递推 f[i]=f[i-1]+f[i/2];
边界 f[0]=1;
答案 f[n/2];
高精只压了4位(万进制),每个点都是560ms....

编译成功

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
45 lines compiled, 0.1 sec , 29248 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 904 ms, mem = 82932 KiB, score = 10
测试数据 #1: Accepted, time = 858 ms, mem = 82932 KiB, score = 30
测试数据 #2: Accepted, time = 889 ms, mem = 82932 KiB, score = 60
Accepted, time = 2651 ms, mem = 82932 KiB, score = 100

程序如下...
type num=array[0..13] of longint;
const mm=1000000000;
var n,len,k,i:longint;
f:array[0..1500100] of num;
procedure add(var a,b:num);
begin
if a[0]>b[0] then len:=a[0]
else len:=b[0];
for k:=1 to len do begin
inc(a[k],b[k]);
inc(a[k+1],a[k]div mm);
a[k]:=a[k] mod mm;
end;
if a[len+1]<>0 then inc(len);
a[0]:=len;
end;

procedure pt(n:longint);
var i:longint;
begin
write(f[n div 2,f[n div 2,0]]);
for i:=f[n div 2][0]-1 downto 1 do begin
if f[n div 2][i]<100000000 then write(0);
if f[n div 2][i]<10000000 then write(0);
if f[n div 2][i]<1000000 then write(0);
if f[n div 2][i]<100000 then write(0);
if f[n div 2][i]<10000 then write(0);
if f[n div 2][i]<1000 then write(0);
if f[n div 2][i]<100 then write(0);
if f[n div 2][i]<10 then write(0);
write(f[n div 2][i]);
end;
end;

begin
f[0][0]:=1;f[0][1]:=1;
for i:=1 to 1500000 do begin
add(f[i],f[i-1]);
add(f[i],f[i div 2]);
end;
while not eof do begin
readln(n);
pt(n);
writeln;
end;
end.

恶心的卡内存！！

上海红茶馆 via JudgeDaemon2/13.4.1.0 via libjudge
编译成功

foo.cpp:5:21: warning: missing braces around initializer for 'int [6]' [-Wmissing-braces]
测试数据 #0: Accepted, time = 31 ms, mem = 70676 KiB, score = 10
测试数据 #1: Accepted, time = 132 ms, mem = 70676 KiB, score = 30
测试数据 #2: Accepted, time = 171 ms, mem = 70676 KiB, score = 60
Summary: Accepted, time = 334 ms, mem = 70676 KiB, score = 100
代码
#include<iostream>
#include<cstdio>
using namespace std;
const int n=1000000000;
int f[3000000][6]={0};
int a[50]={0};
int maxn,k;
void init()
{
int i;
i=0;
maxn=0;
while(cin>>a[i])
{
if(maxn<a[i])maxn=a[i];
i++;
}
k=i;

}
void pluss(int a[],int b[],int c[])
{
int i;
for(i=0;i<6;i++)
{
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/n;
c[i]=c[i]%n;
}
}
void solve()
{
int i,j;
f[0][0]=1;
f[1][0]=1;
for(i=2;i<=maxn;i++)
{

if(i%2!=0)
{
for(j=0;j<6;j++)
f[i][j]=f[i-1][j];
continue;
}
pluss(f[i-1],f[i/2],f[i]);
}
}
void print()
{
int i,j,l;
for(i=0;i<k;i++)
{
j=5;
while ((f[a[i]][j]==0)&&(j>0))j--;
cout<<f[a[i]][j];
for(l=j-1;l>=0;l--)
{
if(f[a[i]][l]/100000000==0) cout<<'0';
if(f[a[i]][l]/10000000==0) cout<<'0';
if(f[a[i]][l]/1000000==0) cout<<'0';
if(f[a[i]][l]/100000==0) cout<<'0';
if(f[a[i]][l]/10000==0) cout<<'0';
if(f[a[i]][l]/1000==0) cout<<'0';
if(f[a[i]][l]/100==0) cout<<'0';
if(f[a[i]][l]/10==0) cout<<'0';
cout<<f[a[i]][l];
}
cout<<endl;
}
}
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);

init();
solve();
print();
return 0;
}

f[i]:=f[i div 2]+f;

三个优化

1.只记录偶数项 所以把n：=n div 2 f[i]:=f+f[i div 2];

2.高精度压10位

3.先算数据中最大的 比他小的就不必再算 直接输出f即可

三个优化=秒杀

高精度是个问题啊 费了不时间 好歹最后写了个简洁明了的

贴一下

const oo=10000;

type arr=array[0..21] of longint;

var f:array[0..1500000] of arr;

　　a,b,c:arr;

　　i,j,n,l,max:longint;

procedure calc(var c,a,b:arr);

var i,j:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to 20 do

begin

　　c:=c+(a[i]+b[i]) div oo;

　　c[i]:=c[i]+(a[i]+b[i]) mod oo;

end;

end;

procedure print;

var i,j:longint;

begin

for i:=20 downto 1 do

if f[n,i]0 then break;

write(f[n,i]);

dec(i);

for j:=i downto 1 do

begin

if f[n,j]

好猥琐的题目

超级压位，看看这个吧，压了18位（如有雷同，纯属无聊）

const maxn=3000000;

mom=1000000000000000000;

type atype=array[0..3]of int64;

var i,j,k,n,max:Longint;

sum:array[0..maxn shr 1]of atype;

num:array[0..24]of longint;

procedure print(a:atype);

var i,j:Longint;

K:int64;

begin

write(a[a[0]]);

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

begin

k:=mom div 10;

repeat

write(a[i] div k mod 10);

k:=k div 10;

until k=0;

end;

end;

procedure add(var a:atype;b:atype);

var i,j:longint;

k:int64;

begin

if a[0]0 then

begin

inc(a[0]);

a[a[0]]:=k;

end;

end;

begin

fillchar(num,sizeof(num),0);

max:=0;

repeat

inc(num[0]);

readln(num[num[0]]);

if num[num[0]]>max then max:=num[num[0]];

until eof;

n:=max;

fillchar(sum[0],sizeof(sum[0]),0);

sum[0,0]:=1;

sum[0,1]:=1;

for I:=1 to n shr 1 do

begin

sum[i]:=sum[i shr 1];

add(sum[i],sum);

end;

for i:=1 to num[0] do

begin

print(sum[num[i] shr 1]);

writeln;

end;

end.

太猥琐.....

交了7遍,,!

直到不能再什么嘛……破题！

超级压位~~ 256进制

Program Vijos_P1136;

Var

a: Array [0..3000000] Of Array [0..22] Of Byte;

b, c: Array [0..51] Of Byte;

y: Array [1..1000] Of dWord;

i, j, t, n, x, z: dWord; w: Word;

Begin

n:=0; z:=0;

While Not(Eof) Do Begin

Inc(z); ReadLn(y[z]); y[z]:=y[z] Shr 1;

If y[z]>n Then n:=y[z]

End;

FillByte(a[0], 23, 0);

a[0][0]:=1; a[0][1]:=1;

For i:=1 To n Do Begin

FillByte(a[i], 23, 0);

t:=i Shr 1; w:=0; a[i][0]:=a[0];

For j:=1 To a[i][0]+1 Do Begin

Inc(w, a[j]+a[t][j]);

a[i][j]:=Lo(w); w:=Hi(w)

End;

If a[i][a[i][0]+1]>0 Then Inc(a[i][0])

End;

For x:=1 To z Do Begin

n:=y[x];

FillByte(b, 52, 0); FillByte(c, 52, 0);

b[0]:=1; b[1]:=1;

For i:=1 To a[n][0] Do Begin

w:=0;

For j:=1 To b[0]+3 Do Begin

Inc(w, a[n][i]*b[j]);

Inc(c[j], w Mod 10);

Inc(c[j+1], c[j] Div 10); c[j]:=c[j] Mod 10;

w:=w Div 10

End;

w:=0;

For j:=1 To b[0]+3 Do Begin

Inc(w, b[j] Shl 8);

b[j]:=w Mod 10;

w:=w Div 10

End;

Inc(b[0], 3); While b[b[0]]=0 Do Dec(b[0])

End;

c[0]:=51; While c[c[0]]=0 Do Dec(c[0]);

For j:=c[0] DownTo 1 Do Write(c[j]);

WriteLn

End

End.