Byfibonacci

Fibonacci Sequence:

$f_0=1\\ f_1=1\\ f_i=f_{i-1}+f_{i-2}, i≥2$

Fibonacci representation $F(x)_{}$ : Any natural number $x_{}$ can be expressed as the sum of a set of different Fibonacci numbers.

In particular: $f_0$ and $f_1$ are two different Fibonacci numbers.

For example: $7=5+2=f_4+f_2, \ 7=3+2+1+1=f_3+f_2+f_1+f_0$ indicates that $7_{}$ corresponds to at least two Fibonacci representations.

The value of the Fibonacci representation $w(F(x))_{}$ : defined as the product of the Fibonacci numbers in the representation .

For example: $7=3+2+1+1=f_3+f_2+f_1+f_0$ . In this representation, the value $w(F(x))_{}$ is: $3*2*1* 1=6_{}$ .

With the above definitions, now, find the sum of all Fibonacci representations’ value of a given number $x_{}$ .

To simplify the question, please output the answer modulo lovely $998244353_{}$ .

#include<bits/stdc++.h> using namespace std; const int mod=998244353; int f[50]; int dp[10000005]; int main(){ f[0]=1;f[1]=1; for (int i=2;i<=34;++i){ f[i]=f[i-1]+f[i-2]; } dp[0]=1; dp[1]=1; for (int i=1;i<=34;++i){ for (int j=min(10000005,3*f[i]);j>=f[i];j--){ dp[j]=(dp[j]+(1ll*dp[j-f[i]]*f[i])%mod)%mod; } } int t; scanf("%d",&t); while(t--){ int x; scanf("%d",&x); printf("%d\n",dp[x]); } }

详情