fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define C make_pair
  3. #define ll long long
  4. #define all(a) a.begin(),a.end()
  5. #define name "task"
  6. #define ln "\n"
  7. using namespace std;
  8. ll n;
  9. const ll oo=1e14,mod=1e9+7;
  10. vector<ll> fibo;
  11. map<ll,ll> mp;
  12. void sieve_fibo(){
  13. 	ll f1=0,f2=1;
  14. 	ll f3=0; //++mp[1LL];
  15. 	while(f3<oo){
  16. 		f3=f1+f2;
  17. 		f1=f2; f2=f3;
  18. 		//++mp[f3];
  19. 		fibo.push_back(f3);
  20. 		//cout<<f3<<ln;
  21. 	}
  22. }
  23. void add(ll &a,ll b){
  24. 	a+=b;
  25. 	if(a>=mod)
  26. 		a-=mod;
  27. }
  28. void solve(){
  29. 	cin>>n;
  30. 	sieve_fibo();
  31. 	vector<ll> a(n+9),pre(n+9,0);
  32. 	for(int i=1;i<=n;++i){
  33. 		cin>>a[i];
  34. 		pre[i]=pre[i-1]+a[i];
  35. 	}
  36. 	vector<ll> dp(n+9,0);
  37. 	dp[0]=1;
  38. 	for(int i=1;i<=n;++i){
  39. 		for(ll f:fibo){
  40. 			ll l=1,r=i,pos=-1;
  41. 			while(l<=r){
  42. 				ll mid=l+r>>1;
  43. 				if(pre[i]-pre[mid-1]>=f){
  44. 					pos=mid;
  45. 					l=mid+1;
  46. 				} else{
  47. 					r=mid-1;
  48. 				}
  49. 			}
  50. 			if(pos==-1){
  51. 				break;
  52. 			} else if(pre[i]-pre[pos-1]==f){
  53. 				add(dp[i],dp[pos-1]);
  54. 			}
  55. 		}
  56. 	}
  57. 	cout<<dp[n];
  58. }
  59. int main(){
  60.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  61.     if(fopen(name".inp","r")){
  62.         freopen(name".inp","r",stdin);
  63.         freopen(name".out","w",stdout);
  64.     }
  65.     solve();
  66. }
  67.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5
2 5 3 1 2
stdout
copy 
5
https://ideone.com/G7JfYK
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!