自动搬运

查看原文

来自洛谷，原作者为

	RKcer21 这个蒟蒻很懒，什么也没有留下

搬运于2025-08-24 22:17:03，当前版本为作者最后更新于2020-02-15 20:08:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

（附赠作者打的表）

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

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

别急，我们把这些数字列进表格里来看 | n=|1 |2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 | 12| | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | f(n)= | 1 |2 | 2 | 4 | 4 | 6 | 6 | 10 | 10 | 14 | 14 | 20 |

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

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;
}

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