题解 P6065 【[USACO05JAN]Sumsets S】

· · 题解

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

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

（附赠作者打的表）

f(1)=1,f(2)=2, f(3)=2, f(4)=4,f(5)=4 f(6)=6, f(7)=6, f(8)=10, f(9)=10,f(10)=14 f(11)=14, f(12)=20

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

f(n)=f(n-1)

那么，对于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为偶数时:

f(n)=f(n-1)+f(n/2)

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

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

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