tle in spoj fibonomial

#include
#include
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define MOD 1000000007
#define sqrit(x) ((x) * (x))
using namespace std;
void fastFibo(long long int n, pair<long long int, long long int>& vals){
if(n == 0){
vals.first = 0;
vals.second = 1;
return;
}
fastFibo(n/2, vals);
long long int ev, od;
ev = 2 * vals.second - vals.first;
if(ev < 0) ev += MOD;
ev = (ev * vals.first)%MOD;
od = (sqrit(vals.first) + sqrit(vals.second))%MOD;
if(n%2 == 0){
vals.first = ev;
vals.second = od;
} else {
vals.first = od;
vals.second = od + ev;
}
}

 int main(){
        fastio
    	int t;
    	cin>>t;
      	pair<long long int, long long int> vals;
     	vals.first = vals.second = 0;
  	while(t--){
        	long long int n, x, res;
          		res = 0;
        	cin>>n>>x;
     		for(int i = n; i > 0; --i){
        			fastFibo(i, vals);
          		res = (x*((res + vals.first)%MOD))%MOD;
        		}
     		cout<<res<<endl;
    	}
    	return 0;
   }

http://www.spoj.com/problems/FIBONOMIAL/

I think this Page should definitely help you… If you still face problem, I will explain in more detail but you try it first… :slight_smile:

Please provide problem link too along with name…

link added

n can be upto 10^{15} so will not It give tle for obvious reasons… I mean you are just iterating over n… Are you asking for better algorithm to solve it??

yes, is there a way to reduce the complexity and do it without iteration
or any other way??

still can’t understand