Experimentation. Like I don’t think I have seen a list of such useful formulas anywhere; although it woud be nice if such a list existed.
i saw the solution from the video editorial and I didn’t understand one thing what’s the use of %MOD like he is storing double of previous answers
That is if n = 4, so it is storing ans[3] × 2 at n = 4
Ans of n = 4 is …4× 2 = 8. I don’t get what’s the use of MOD here? like there was given in the Q to use 10^9+7 since the input were larget but what is the use of MOD in this line ?
" ans[i] = (ans[i-1]*2)% MOD; "
#include
using namespace std;
const int MX = 1e5 + 5; //since in Q it is given at max it will go it here
const int MOD = 1e9 + 7;
vectorans(MX);
void pre(){
ans[1]=1;
for(int i=2; i<MX; i++)
ans[i] = (ans[i-1]*2)% MOD;
}
int main(){
pre();
int t;cin>>t;
while(t--){
int n; cin>>n;
cout<<ans[n]<<endl;
}
return 0;
}