#include <iostream>
#include <queue>
#include <stack>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <cmath>
#include <cassert>
#include <unordered_set>
#include <map>
#include <deque>
#include <unordered_map>
#include <fstream>
#include <set>
#include <algorithm>
#include <iomanip>
#define fin cin
#define fout cout
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
ll dp[maxn][100], f[100];
int main () {
ios_base::sync_with_stdio(false);
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= 50; i++)
f[i] = f[i - 1] + f[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 < int (1e5); i++) {
for (int j = 1; j <= 50; j++) {
dp[i][j] = dp[i][j - 1];
if (f[j] <= i)
dp[i][j] += dp[i - f[j]][j - 1];
dp[i][j] %= mod;
}
}
int n;
cin >> n;
ll sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += f[x];
cout << dp[sum][50] << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
78660 KB |
Output is correct |
2 |
Correct |
128 ms |
78720 KB |
Output is correct |
3 |
Correct |
126 ms |
78896 KB |
Output is correct |
4 |
Correct |
127 ms |
78896 KB |
Output is correct |
5 |
Correct |
125 ms |
78896 KB |
Output is correct |
6 |
Correct |
127 ms |
78896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
78660 KB |
Output is correct |
2 |
Correct |
128 ms |
78720 KB |
Output is correct |
3 |
Correct |
126 ms |
78896 KB |
Output is correct |
4 |
Correct |
127 ms |
78896 KB |
Output is correct |
5 |
Correct |
125 ms |
78896 KB |
Output is correct |
6 |
Correct |
127 ms |
78896 KB |
Output is correct |
7 |
Correct |
127 ms |
78896 KB |
Output is correct |
8 |
Runtime error |
235 ms |
157296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
237 ms |
157584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
78660 KB |
Output is correct |
2 |
Correct |
128 ms |
78720 KB |
Output is correct |
3 |
Correct |
126 ms |
78896 KB |
Output is correct |
4 |
Correct |
127 ms |
78896 KB |
Output is correct |
5 |
Correct |
125 ms |
78896 KB |
Output is correct |
6 |
Correct |
127 ms |
78896 KB |
Output is correct |
7 |
Correct |
127 ms |
78896 KB |
Output is correct |
8 |
Runtime error |
235 ms |
157296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
262 ms |
157584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
78660 KB |
Output is correct |
2 |
Correct |
128 ms |
78720 KB |
Output is correct |
3 |
Correct |
126 ms |
78896 KB |
Output is correct |
4 |
Correct |
127 ms |
78896 KB |
Output is correct |
5 |
Correct |
125 ms |
78896 KB |
Output is correct |
6 |
Correct |
127 ms |
78896 KB |
Output is correct |
7 |
Correct |
127 ms |
78896 KB |
Output is correct |
8 |
Runtime error |
235 ms |
157296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |