[洛谷 3424][POI2005]Fibonacci Sums

题目链接

https://www.luogu.org/problem/P3424

题解

一道小清新数论题。

我们把两个数加起来，会出现这样几种不合法的情况：

1. 连续两个位上的值都是 1；
2. 一个数位上的值为 2。

对于第一种情况，我们直接利用 \(f_i=f_{i-1}+f_{i-2}\) 处理即可。

对于第二种情况：我们发现 \(2f_i=f_i+f_i=f_i+f_{i-1}+f_{i-2}=f_{i+1}+f_{i-2}\)，因此可以根据这条性质解决第二种情况。（特别地，\(2f_2=f_1+f_3\)，\(2f_1=f_2\)）

我们从高位到低位按顺序处理这两种不合法的情况即可。

注意我们处理处理当前位的时候，可能导致之前处理过的较高位再次出现不合法情况，因此我们每次处理完一位之后都要再这一位前面的两位产生的不合法情况进行处理。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[1000005],b[1000005],ans[1000005];
void dec(int x)
{
 ans[x]-=2;
 if(x==1)ans[2]++;
 else if(x==2)ans[1]++,ans[3]++;
 else ans[x-2]++,ans[x+1]++;
}
void add(int x)
{
 while(ans[x]&&ans[x+1])
 {
  ans[x]--,ans[x+1]--,ans[x+2]++;
  x+=2;
 }
}
int main()
{
 int x,y;
 scanf("%d",&x);
 for(int i=1;i<=x;i++)
  scanf("%d",&a[i]);
 scanf("%d",&y);
 for(int i=1;i<=y;i++)
  scanf("%d",&b[i]);
 int len=max(x,y);
 for(int i=1;i<=len;i++)
  ans[i]=a[i]+b[i];
 for(int i=len;i;i--)
 {
  if(ans[i]>1)dec(i);
  add(i);
  if(ans[i+1]>1)dec(i+1);
  add(i+1);
  if(ans[i+2]>1)dec(i+2);
  add(i+2);
 }
 if(ans[len+1])len++;
 if(ans[len+2])len+=2;
 printf("%d ",len);
 for(int i=1;i<=len;i++)
  printf("%d ",ans[i]);
 return 0;
}