前面的作者好像很强，连打表找规律这一个方法都没有用到，那本蒟蒻就来写一波由打表找出规律的方法:

这题一看题目，就是数论之类的东西，所以作者的本能反应，就是打表找规律（打表大法好啊）。

（附赠作者打的表）

初看上面这一张表，我们会发现，除了1之外，所有n为奇数时:

那么，对于$n$为偶数时，$f(n)$又有什么规律呢？

别急，我们把这些数字列进表格里来看

欸，好像这些数字都存在着关系:

2好像是由1+1得来的

4好像是由2+2得来的

6好像是由2+4得来的

10好像是由4+6得来的

...

再仔细观察一下这组数的特点，就可以得出，当n为偶数时:

好的，这就可以写出这题了。（附上代码）

#include<bits/stdc++.h>
using namespace std;
long long s[1000001];
#define N 1000000000
int i,j,k,n;
int main()
{
  cin>>n;
j=1;
k=1;
s[0]=1;
  for (i=1;i<=n;i++)
   {
    if (i%2==1) s[i]=s[i-1];
      else s[i]=(s[i-1]+s[i/2])%N;
   }
cout<<s[n];
  return 0;
}

好的，让我们总结一下。 有些时候，我们并不能一眼看出公式（尤其是像我这么弱的人），所以这个时候，我们需要打表去观察，运用适合的方法，去找到那彼岸的规律。