NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#191228	#2733. 8.4t3	wosile	100	317ms	9796kb	C++	564b	2023-10-08 11:28:15	2023-10-08 12:42:21

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[105];
map<pair<ll,int>,int>dp;
int dfs(ll n,int d){
	if(f[d+2]-2<n)return 0;
	if(d==1)return 1;
	if(n==0)return 1;
	pair<ll,int>p=make_pair(n,d);
	if(dp.find(p)!=dp.end())return dp[p];
	if(n>=f[d])dp[p]+=dfs(n-f[d],d-1);
	dp[p]+=dfs(n,d-1);
	return dp[p];
}
int main(){
	f[0]=f[1]=1;
	for(int i=2;i<=90;i++)f[i]=f[i-1]+f[i-2];
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		printf("%d\n",dfs(n,87));
	}
	return 0;
	//quod erat demonstrandum
}

源文件, 语言: C++

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 14ms

memory: 5132kb

input:

output:

result:

ok 1000 numbers

Test #2:

score: 10

Accepted

time: 18ms

memory: 5388kb

input:

output:

result:

ok 1000 numbers

Test #3:

score: 10

Accepted

time: 13ms

memory: 5632kb

input:

output:

result:

ok 1000 numbers

Test #4:

score: 10

Accepted

time: 24ms

memory: 6328kb

input:

output:

result:

ok 1000 numbers

Test #5:

score: 10

Accepted

time: 30ms

memory: 6516kb

input:

output:

result:

ok 1000 numbers

Test #6:

score: 10

Accepted

time: 34ms

memory: 7116kb

input:

output:

result:

ok 1000 numbers

Test #7:

score: 10

Accepted

time: 36ms

memory: 7376kb

input:

output:

result:

ok 1000 numbers

Test #8:

score: 10

Accepted

time: 76ms

memory: 9256kb

input:

1000
384997060794894
3052576495984458
2515613738333319
2758137799841781
2771826157513722
25973702479...

output:

result:

ok 1000 numbers

Test #9:

score: 10

Accepted

time: 71ms

memory: 9796kb

input:

1000
438790986257646999
739257800188095523
841238673343474427
320309202621474808
554464838878161478
...

output:

result:

ok 1000 numbers

Test #10:

score: 10

Accepted

time: 1ms

memory: 1392kb

input:

output:

result:

ok 30 numbers