MATBREAK
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
const long long mod = 1000000007;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, a;
cin >> n >> a;
long long temp = 1, power = 1;
vector <long long> pows(n);
pows[0] = 1;
for (int i = 1; i < n; ++i)
{
pows[i] = (temp+power)*((2*(i))+1);
temp += power;
power = pows[i];
}
unsigned long long s = 0;
for (int i = 0; i < n; ++i)
{
s += pow(a, pows[i]);
}
cout << (s % mod) << '\n';
}
}
This works fine for the sample test cases. It gives a WA verdict though. How do I fix this?
You can’t use pow for exponentiation. Search up modular exponentiation.
1 Like
I tried that too, but I got WA.
Just because you get wrong answer with modular exponentiation also, Doesn’t mean you can use pow.
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p =1e9 + 7;
long long int modpower(ll b,ll po, ll mod=p){
long long int ans=1;
while(po){
if(po&1){
ans*=b;
ans%=mod;
}
b*=b;
b%=mod;
po>>=1;
}
return ans;
}
ll solve(){
ll n, a;
cin>>n>>a;
ll ans=0;
for(int i=1;i<=n;i++){
ans+=modpower(a, 2*i - 1);
ans%=p;
a*=modpower(a, 2*i -1);
a%=p;
}
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
solve();
}
}
That’s literally all you need to do.
Your code is overflowing everywhere.
You are multiplying by (2i +1) from 1 to n, that will overflow pows[i]
Then you are using pow, which returns a double, so is inaccurate. Then you are not taking mod, so s will overflow there as well.
1 Like
Thanks, I understood. Can you please explain the use of bitwise operators in modpower()
?
Let’s say we want to find x^{13}.
First we write it as x^8 * x^4 * x, which is like 1101. Since the leftmost bit is 1, we have to multiply by x^1. Now we do a right shift and get 110. The leftmost bit is 0, so we don’t multiply by x^2. Another right shift and we get 11. Leftmost bit is 1, so we multiply by x^4, Then the last right shift, we get 1, and we multiply by x^8.
1 Like