Submission #112393

#TimeUsernameProblemLanguageResultExecution timeMemory
112393redaFibonacci representations (CEOI18_fib)C++14
5 / 100
266 ms157176 KiB
#include <bits/stdc++.h> #define MAXN 100005 #define MOD 1000000007 using namespace std; long long dp[MAXN][100], fib[100]; long long X (int pk) { return dp[pk][50]%MOD; } void precompute() { fib[1]=1; fib[2]=2; for (int i=3;i<=50;i++) fib[i]=fib[i - 1]+fib[i - 2]; for (int i=0;i<=50;i++) { dp[1][i]=1; dp[0][i]=1; } dp[1][0]=0; for (int i=2;i<100000;i++) { for (int j=1;j<= 50;j++) { dp[i][j]=dp[i][j - 1]%MOD; if (fib[j] <= i)dp[i][j]+=(dp[i - fib[j]][j - 1])%MOD; dp[i][j]%=MOD; } } } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); precompute(); int n; cin>>n; long long pk=0; while(n--) { int x; cin>>x; pk+=fib[x]; cout<<X(pk)<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...