Description：

给出 $n$ ，求： $$ \sum_{x_1+x_2+\cdots+x_k=n}\prod _{i=1}^kfib(x_i) $$ $1\leqslant n\leqslant10^6$

Solution：

$$ \begin{align} G(n)&=\sum_{x_1+x_2+\cdots+x_k=n}\prod _{i=1}^kfib(x_i)\\ &=\sum_{i=1}^{n-1}G(n-i)\times fib(i)+fib(n)\\ &=\sum_{i=2}^{n-1}G(n-i)\times(fib(i-1)+fib(i-2))+G(n-1)+fib(n-1)+fib(n-2)\\ &=\sum_{i=1}^{n-2}G(n-1-i)\times fib(i)+\sum_{i=1}^{n-2}G(n-1-i)\times fib(i-1)+G(n-1)+fib(n-1)+fib(n-2)\\ &=2G(n-1)+\sum_{i=1}^{n-3}G(n-2-i)\times fib(i-2)+fib(n-2)\\ &=2G(n-1)+G(n-2) \end{align} $$

Code：

#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 1000010

int G[MAXN];

#define MOD 1000000007

int main()

{

	scanf("%d",&n);

	G[0] = 0;G[1] = 1;

	for(int i = 2;i <= n;++i)

	{

		G[i] = (2ll * G[i - 1] + G[i - 2]) % MOD;

	}

	cout << G[n] << endl;

	return 0;

}