Description
先输入一个自然数n(n≤3000000)，然后对此自然数按照如下方法进行处理
1•不作任何处理:
2•在它的左边加上一个自然数，但该自然数不能超过原数的一半;
3•加上数后，继续按此规则进行处理，直到不能再而 自然数为止。
例如
n=6
6
16
26
126
36
136
所以满足要求的个数为6。
Input
一个整数n(1<=n<=3000000)
Output
一个整数,表示解的个数(保证不超过50位)
Sample Input
6
Sample Output
6
分析：
用f[n]表示最后一个数是n时，可以构造出的数的总数。规定f[0]=1，则显然有f[n]=f[0]+f[1]+...+f[n div 2]。
但若直接使用这个方程，则会既TLE又MLE。注意到右边其实是f数组开头若干个元素的和，因此可开一个s数组，用s[n]来存储f[0]至f[n]的和。这样时间上显然没有问题。实际上，现在f数组已经不必要了，因为用s数组可写出如下状态转移方程：s[n]=s[n-1]+f[n]=s[n-1]+s[n div 2]。当读入n时，输出s[n div 2]即可。
结果很大，高精度是当然的。可以用3个int64来存储一个数。这里我们看到用s数组代替f数组同样解决了MLE的问题，因为s数组的大小只有f数组的一半，题目允许的内存不能容纳f数组，却恰好可以容纳s数组。
【参考程序1】：//NOIP 2001 普及组 n<=1000
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int n,ans;
void dfs(int n)
{
ans++;
for (int i=1;i<=n/2;i++)
dfs(i);
}
int main()
{
scanf("%d",&n);
ans=0;
dfs(n);
printf("%d\n",ans);
return 0;
}
【参考程序2】://加强版
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=1500002;
__int64 s[maxn][3];
int n;
void print(__int64 a)
{
char ch[60];
sprintf(ch,"%I64d",a);
for (int i=strlen(ch);i<=17;i++) printf("0");
printf("%s",ch);
}
void cout_ans(__int64 a,__int64 b,__int64 c)
{
if (a>0)
{
printf("%I64d",a);
print(b);print(c);
}
else if (b>0)
{
printf("%I64d",b); print(c);
}
else printf("%I64d",c);
printf("\n");
}
int main()
{
__int64 base;
base=(__int64)(pow(10.0,9.0)); base*=base;
memset(s,0,sizeof(s));
s[0][0]=1;
for (int i=1;i<=maxn;i++)
for (int j=0;j<=2;j++)
{
s[i][j]+=s[i-1][j]+s[i>>1][j];
if (s[i][j]>=base)
{
s[i][j+1]++; s[i][j]-=base;
}
}
while (scanf("%d",&n)!=EOF)
{
n=n>>1;
cout_ans(s[n][2],s[n][1],s[n][0]);
}
return 0;
}
【参考程序】：//pascal
const maxb=1000000000;
maxn=1500000;
var f:array[0..maxn+1,0..7] of longint;
i,j,t,n:longint;
s:string;
begin
f[0,1]:=1;f[0,0]:=1;
for i:=1 to maxn do
begin
f[i]:=f[i-1];
t:=i shr 1;
for j:=1 to f[i,0] do
begin
inc(f[i,j],f[t,j]);
if f[i,j]>=maxb then
begin
inc(f[i,j+1],f[i,j]div maxb);
f[i,j]:=f[i,j] mod maxb;
end;
end;
if f[i,f[i,0]+1]<>0 then inc(f[i,0]);
end;
while not (eof) do
begin
readln(n);
i:=n shr 1;
t:=f[i,0];
write(f[i,t]);
for j:=t-1 downto 1 do
begin
str(f[i,j],s);
while length(s)<9 do s:='0'+s;
write(s);
end;
writeln;
end;
end.