okay thankyou 
Can anyone please tell whats wrong with my solution. It works fine with n=3 & a=2.
But it gives negative answer for n=3 & a=4 and many more cases.
PLEASE HELP!
#include<bits/stdc++.h>
#define ll long long int
#define li long int
using namespace std;
int main()
{
ll n,a;
cin>>n>>a;
ll p[n];
p[1]=a;
for(ll i=2;i<=n;++i)
{
p[i]= pow((p[i-1] * a),(2*i)-1);
a= a*p[i-1];
}
ll tmp=0;
for(ll i=1;i<=n;++i)
tmp+=p[i];
cout<<tmp%1000000007<<"\n";
return 0;
}you should calculate power using your self power function and take modulo%1000000007 at every step, because for large value of a your power function will give 0 as output.
refer this link->Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks
2 Likes
can someone explain me as how can i resolve the issue of evaluating negative no in the pow function…this is my code
#include<bits/stdc++.h>
#define M 1000000007
using namespace std;
long long pow(long long no,long long power)
{
if(power == 1)
return no;
else if(power == 0)
return 1;
long long R = pow(no,power/2)%M;
R = R*R%M;
if(power%2 != 0)
{
R = R*no%M;
}
return R%M;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
long long a;
cin >> n;
cin >> a;
long long no = a;
long long sum = 0;
long long pro;
for(int i = 1;i<=n;i++)
{
pro = pow(no,2*i-1);
//cout << "pro1 : " << pro << endl;
pro = pro%M;
//cout << "pro2 : " <<pro << endl;
if(pro<0)
pro += M;
sum = (sum+pro)%M;
no = (no*pro)%M;
}
cout << sum << endl;
}
return 0;
}
How did you arrive at this series?
https://www.codechef.com/viewsolution/32075109
can somebody help why i was getting TLE in this solution .
Any help would be very very helpful.
Thanks in advance
@rajarshi_basu
Simple video editor of MATBREAK 
Matrix Decomposition || April Cook-Off 2020 Division 2 || c++ solution - YouTube
It gives *** the wrong answer***. Can anyone see my code and tell me what is wrong in my code?
#include<bits/stdc++.h>
#define M 1000000007
typedef long long ll;
using namespace std;
ll expo(ll a , ll b){
ll ans=1;
while(b){
if(b&1){
ans=(ansa)%M;
}
a=(aa)%M;
b>>=1;
}
// cout<<ans<<endl;
return ans;
}
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
ll answer=0;
ll basic=1;
for(int i = 1 ; i <= n ;i++){
ll l=expo(kbasic,2i-1);
l=l%M;
answer=(answer+l)%M;
basic=(basic*l)%M;
// cout<<answer<<endl;
}
cout<< answer%M;
}}
thanks!
It had a minor flaw. I did it.
Thanks anyways.
I guess that power function is not calculating in O(log n) using fast exponentiation. Implement your own and use it. Also, it makes sense to keep mod’n the result more frequently. You should do it in every iteration after the addition.
https://www.codechef.com/viewsolution/32108158
can someone please help me in understanding, why my code is not being able to accept large values ,despite writing it according to the solution mentioned in the editorial.
Thanks in advance 
@rajarshi_basu
Here is my code gyus : I am getting WA. Can someone tell me why?
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
long long int mod = 1e9 + 7;
ll power(ll a, int p){
ll ans = 1;
while(p / 2){
ans = ans *((a * a) % mod);
ans = ans % mod;
p /= 2;
}
if§{
ans = ans * a;
ans = ans % mod;
}
return ans;
}
void solver(){
ll n, a, last = 1, curr;
ll sum = 0;
cin >> n >> a;
curr = a;
if(a == 0){
cout << a << ‘\n’;
return;
}
if(a == 1){
cout << n << ‘\n’;
return;
}
for(int i = 1; i <= n; ++i){
curr = (curr * last) % mod;
last = power(curr, 2 * i - 1);
sum = (sum + last) % mod;
}
cout << sum << ‘\n’;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tc;
cin >> tc;
while(tc–){
solver();
}
return 0;
}
Hey, can anyone please help me find the error in my code. It works fine for N < 10 but somehow fails afterwards. If anyone can explain what’s the problem then it will be a great help.
Thanks in advance
Here’s my code :
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll power(ll x, ll y)
{
ll res = 1;
x = x % mod;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1)
res = (res*x) % mod;
y = y >> 1;
x = (x*x) % mod;
}
return res;
}
int main() {
// your code goes here
int t;
cin >> t;
while(t--)
{
ll n,a,i,j,o=3,temp;
cin >> n >> a;
ll dp[n+1];
dp[0]=0;
dp[1]=1;
temp=1;
for(i=2;i<=n;i++)
{
dp[i]=(temp+1)%mod;
dp[i]=((dp[i]%mod)*(o%mod))%mod;
temp = (dp[i]+temp)%mod;
o+=2;
}
ll sum=0;
for(i=1;i<=n;i++)
sum = ( (sum%mod) + power(a,dp[i]) ) % mod;
cout << sum << endl;
}
return 0;
}
My code worked for the sample testcase, but still getting WA. What is wrong with my code?
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
//typedef unsigned long long ll;
int main(){
ll t;
cin>>t;
while(t--)
{
ll n,a;
cin>>n>>a;
n = n*n;
ll M = 1000000007;
ll p=0,res=0;
for(int i=1;i<=n;i++)
{
ll temp = 2*i - 1;
p = (ll)(pow(a,temp)+0.5);
a = a*p;
n = n - temp;
res += p;
//cout<<temp<<" "<<p<<" "<<a<<" "<<n<<endl;
}
cout<<res%M<<endl;
}
}
why would you think about the negative power for this question.As the constraints give you only positive numbers then how can you get some negative power to calculate.
1 Like
Because you used inbuilt pow to find the powers it won’t give you the right answer for the constraints more than 10^9 and your answer will be wrong.Use function to calculate modular exponentiation.
1 Like
actually,for inputs t=1 and N=3 A=3, for 3 iteration pow(6561,5) is called leading to some negative values during this evaluation. I don’t know as to why my answer is coming wrong…probably this is the reason…please help
Great Explanation.Thanks @apurv3011. It is better than official editorials.Keep posting more video on CP…Sunscribed your channel…
1 Like