WA in MATBREAK (Matrix Decomposition)

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

Thanks :slightly_smiling_face: