ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214859 | #2733. 8.4t3 | STASISZHY | 40 | 76ms | 110648kb | C++11 | 1.3kb | 2024-11-22 19:59:46 | 2024-11-22 23:13:31 |
answer
// Problem: D. 8.4t3
// Contest: undefined - NOIP2024训练赛 12
// URL: http://noi.ac/contest/1164/problem/2733
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, q, ans;
int dp[N][70], sum[80];
vector<int> v;
inline void init()
{
memset(dp, -1, sizeof dp); v.push_back(0);
for(int i = 0; i <= 65; i ++) dp[0][i] = 1;
int a = 1, b = 1; v.push_back(1);
while(1)
{
int c = a + b; if(c > 1e18) break;
v.push_back(c), a = b, b = c;
}
for(int i = 1; i <= 50; i ++) sum[i] = sum[i - 1] + v[i];
}
int dfs(int now, int flag)
{
// if(!now) return 1;
if(flag <= 50 && now > sum[flag - 1]) return 0;
if(now <= 200000 && ~dp[now][flag]) return dp[now][flag];
int res = 0;
for(int i = flag - 1; ~ i; i --)
{
if(v[i] > now) continue;
res += dfs(now - v[i], i);
}
if(now <= 200000) dp[now][flag] = res;
return res;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int T; cin >> T;
while(T --)
{
cin >> n;
cout << dfs(n, v.size()) << '\n';
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 11ms
memory: 110644kb
input:
1000 571 1996 864 740 2193 2186 1327 1298 1473 1164 615 867 1434 2176 442 1533 813 1090 847 1392 954...
output:
18 22 20 7 8 24 22 20 6 5 11 25 16 34 13 11 10 24 9 12 12 10 9 8 21 17 18 24 14 10 3 27 12 10 3 26 2...
result:
ok 1000 numbers
Test #2:
score: 0
Wrong Answer
time: 8ms
memory: 110644kb
input:
1000 3356 1171 136 1062 3011 1035 572 3025 1649 2608 912 2332 2317 3454 1638 1219 2158 2577 3029 158...
output:
36 25 7 7 48 20 9 34 17 28 18 19 32 40 9 2 30 13 39 17 27 2 4 16 32 6 20 36 20 20 38 16 15 18 40 14 ...
result:
wrong answer 151st numbers differ - expected: '28', found: '25'
Test #3:
score: 0
Wrong Answer
time: 7ms
memory: 110644kb
input:
1000 2050 378 4960 4668 2948 1963 2018 292 2678 2495 101 2950 4914 1251 2319 3253 1537 4206 676 2037...
output:
34 6 25 48 36 18 24 6 28 20 3 24 44 18 24 18 26 12 21 42 7 40 32 37 51 32 14 24 11 24 23 35 14 21 40...
result:
wrong answer 110th numbers differ - expected: '26', found: '19'
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 110640kb
input:
1000 104219 800 26539 61330 5714 5364 31307 19569 81083 92568 123288 53335 80239 107835 102985 2248 ...
output:
180 8 60 132 22 40 96 48 169 88 125 147 56 110 96 12 35 96 210 61 160 65 63 36 49 180 39 18 120 90 6...
result:
wrong answer 498th numbers differ - expected: '104', found: '98'
Test #5:
score: 0
Wrong Answer
time: 7ms
memory: 110640kb
input:
1000 157832 190060 170249 203038 145928 276268 181737 444496 14683 311941 19456 60574 361256 209132 ...
output:
144 120 182 17 76 257 234 294 68 146 36 168 216 290 147 51 275 95 84 204 144 85 100 67 140 287 384 2...
result:
wrong answer 875th numbers differ - expected: '180', found: '228'
Test #6:
score: 10
Accepted
time: 20ms
memory: 110644kb
input:
1000 14080208 88545879 19525576 73869550 29790859 35683476 34070290 55040452 41239264 80671558 34083...
output:
819 2968 448 3654 330 900 2172 1870 2020 1520 2160 495 4446 1891 1512 1008 450 2058 1170 1260 4032 1...
result:
ok 1000 numbers
Test #7:
score: 10
Accepted
time: 16ms
memory: 110648kb
input:
1000 440550064 431992015 780562848 560891500 136906959 874374877 803701364 912120737 617697408 81277...
output:
1320 2988 3666 2704 7200 13312 2313 6816 4160 4095 6336 3642 9261 4608 3780 1050 11616 2520 2478 598...
result:
ok 1000 numbers
Test #8:
score: 0
Time Limit Exceeded
input:
1000 384997060794894 3052576495984458 2515613738333319 2758137799841781 2771826157513722 25973702479...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
1000 438790986257646999 739257800188095523 841238673343474427 320309202621474808 554464838878161478 ...
output:
result:
Test #10:
score: 10
Accepted
time: 4ms
memory: 110636kb
input:
30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
output:
1 1 2 1 2 2 1 3 2 2 3 1 3 3 2 4 2 3 3 1 4 3 3 5 2 4 4 2 5 3
result:
ok 30 numbers