2173: 整数的lqp拆分

题目链接

题目大意：给出输出n。设一种拆分为n=x1+x2+x3，那么这种拆分的价值为F(x1)*F(x2)*F(x3)，F为斐波那契额数列。求所有拆分的价值之和。

题解：Orz Orz

我的收获：强啊

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define md 1000000007 #define ll long long #define inf (int) 1e9 #define eps 1e-8 #define N 1000010 using namespace std; ll f[N]; int main() { int n; scanf("%d",&n); f[0]=0; f[1]=1; for (int i=2;i<=n;i++) f[i]=(2*f[i-1]+f[i-2])%md; printf("%lld\n",f[n]); return 0; }