UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214859#2733. 8.4t3STASISZHY4076ms110648kbC++111.3kb2024-11-22 19:59:462024-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