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
Guys I am getting WA, but the test case is running. Please have a look.
#include<bits/stdc++.h>
using namespace std;int main()
{
int t;
cin>>t;
while(t!=0)
{
t–;
long long int a,n;
cin>>n>>a;long long int prod[n];//store all p's in this array long long int temp=0; prod[0]=a; for(int i=1;i<n;i++) { temp=(prod[i-1]*(int(pow(a,i)))); prod[i]=(pow(temp,(2*(i+1)-1))); } long long int sum=0; for(int i=0;i<n;i++) { sum=(sum+prod[i])%(1000000007); } cout<<sum<<endl;}
return 0;
}
I am taking modulus after adding one p to other for every p(i), but still it’s showing WA only.
I figured out the sequence easily. But was not sure how I would hold such a big number which increases substantially in each step. The answer is using powers. Thanks!
And this is amazing source.
1 Like
Time Complexity of modular exponentiation is O(logy). Now if you are changing power every time you are increasing time every time. rather what you can do is use the result calculated in last step to reduce the time. in first step,p1=a then p2=a^6, p3=a^40. So while calculating p3 you can use result calculated in p2. So you won’t be doing extra calculations
Then there may be something wrong in your logic of code. Try to dry run your code and point out the mistakes. 
I did bro. I added the modular function for power calculation, but still it’s not working. I added mod everywhere possible just to check but still it didn’t work, even though the test case ran every single time. Please have a look at my code
#include<bits/stdc++.h>
using namespace std;
int power(long long int x, long long int y) //X^P MOD P
{
long long int res = 1;
long long int p=1000000007;
x = x % p;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res%p;
}
int main()
{
int t;
cin>>t;
long long int p=1000000007;
while(t!=0)
{
t--;
long long int a,n;
cin>>n>>a;
//vector<vector<int>> v(n,vector<int> (n,a));
long long int prod[n];//store all p's in this array
long long int temp=0;
prod[0]=a;
for(int i=1;i<n;i++)
{
temp=(prod[i-1])*(power(a,i));
prod[i]=power(temp,(2*(i+1)-1));
}
long long int sum=0;
for(int i=0;i<n;i++)
{
sum=(sum+prod[i])%p;
}
cout<<sum<<endl;
}
return 0;
}There is no problem with your power function, it worked perfectly.
Check out this main code.
unsigned long long ans=0;
long long count =1;
while(N–>0){
unsigned long long cal= selfPow(A,count) ;
cal = cal%1000000007;
ans = (ans+cal)%1000000007;
A = (Acal)%1000000007;*
count = count+2;
}
cout<<ans<<endl;
1 Like
Does CodeChef support BOOST library for C++ using which we can use cpp_int_ data type to fit in large numbers and do this question without “Fast Modulo Exonentiation” ?
Thanks
integer overflow takes place in that case since the numbers grow bigger than the range of long long int. so take modulo at each step of exponentiation using a self defined function .
1 Like