题解:
考场上靠打表找规律切的题,不过严谨的数学推导才是本题精妙所在:
求:$sumprod_{i=1}^{m}F_{a{i}}$
设 $f(i)$ 为 $N=i$ 时的答案,$F_{i}$ 为斐波那契数列第 $i$ 项。
由于 $a$ 序列是有序的,要求的答案可以表示成:$f(i)=sum_{j=1}^{i}f(j)*F_{i-j}$
由于斐波那契数列第 0 项是 0,显然可以表示成:
$f(i)=sum_{j=1}^{i-1}f(j)*F_{i-j}$
考虑一下 $f(i+1)$ 和 $f(i)$ 的递推关系:
$f(i+1)-f(i)=sum_{j=1}^{i}f(j)*F_{i-j+1}-sum_{j=1}^{i-1}f(j)*F_{i-j}$
考虑等式右边:
$sum_{j=1}^{i-1}f(j) imes (F_{a_{i}+1-j}-F_{a_{i}-j})+f(i)$
$sum_{j=1}^{i-1}f(j) imes F_{a_{i}-1-j}+f(i)$
$f(i-1)+f(i)$,
于是我们就能推出 $f(i)=2 imes f(i-1)+f(i-2)$
Code:
#include<cstdio> #include<algorithm> #include<string> typedef long long ll; using namespace std; void setIO(string a){ freopen((a+".in").c_str(),"r",stdin); freopen((a+".out").c_str(),"w",stdout); } const ll mod=1e9+7; const int maxn=1000000+5; ll f[maxn],ans[maxn]; int main(){ setIO("math"); int n; scanf("%d",&n); f[0]=0,f[1]=1,ans[1]=1; for(int i=2;i<maxn;++i){ f[i]=f[i-1]+f[i-2]; f[i]%=mod; } for(int i=1;i<n;++i){ ans[i+1]=ans[i]*2+ans[i-1]; ans[i+1]%=mod; } printf("%lld ",ans[n]); return 0; }