Given f(1)=1 , f(2)=1 , and f(n) = 100*f(n-1)+200f(n-2) .
Now , i have to calculate f(n) rof n upto 10^9 , so obvious approach id to use matrix exponentiation ..
I came up with this logic , but it gives wrong output . Can you please explain the reason ?
It fails with n=3 , but i am not able to come up with how to resolve it .
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll m=1000000007;
ll x,y,z,w;
void ml(ll F[2][2],ll M[2][2])
{
x = ((F[0][0]%m)*(M[0][0]%m))%m + ((F[0][1]%m)*(M[1][0]%m))%m;
y = ((F[0][0]%m)*(M[0][1]%m))%m + ((F[0][1]%m)*(M[1][1]%m))%m;
z = ((F[1][0]%m)*(M[0][0]%m))%m + ((F[1][1]%m)*(M[1][0]%m))%m;
w = ((F[1][0]%m)*(M[0][1]%m))%m + ((F[1][1]%m)*(M[1][1]%m))%m;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
//cout<<F[0][0]<<" " <<F[0][1]<<" "<< F[1][0]<<" " <<F[1][1]<<endl;
}
void po(ll F[2][2],ll n)
{
if( n<=1)
return;
ll M[2][2] = {{100,200},{1,0}};
po(F,n/2);
ml(F,F);
if( n%2 != 0 )
ml(F,M);
}
ll f(ll n)
{
ll F[2][2] = {{100,200},{1,0}};
if(n<=2)
return 1;
po(F,n-1);
return F[0][0];
}
int main(){
freopen("input.txt", "rt", stdin);
ll ans,n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%llu",&n);
ans=f(n);
printf("%llu\n",ans);
}
return 0;
}
asked
30 Mar '14, 14:29
2★ac_c0der
72●4●4●8
accept rate:
0%
A few comments and better variable names would be appreciated.
this question is similar to one from an ongoing contest at hackerearth .I would request the admin to temporarily close the question.