Matrix Decomposition | CodeChef

Can someone help me to find out the error??
Edit: April cook off 2020 problem

You are supposed to use modular exponentition and increase i+=2 and not i++…here is my solution

in power function i have used 2*i-1

Then it might because of not using modular exponentition where we return (ans +mod)%mod…may be this might help

I couldn’t find the error. Can u check ??

I think the error lies in your power function. When I used some large numbers to test out your power function, then the values overflow. This is probably why you are getting the wrong answer verdict.
As implemented by @mri_999, you can use modular exponentiation to calculate the powers. When I compared your codes, then there are a few differences here and there and probably that is why you are getting the issue.
You can use another function for faster calculation of power:

long long fast_power(long long base, long long power) {
    long long result = 1;
    while(power > 0) {

        if(power % 2 == 1) { 
            result = (result*base) % MOD;
        base = (base * base) % MOD;
        power = power / 2; // 
    return result;

The complexity for the same will be O(log(power)).
Just by changing your power calculation function, your code works perfectly.

As @harsh0911 noted, your powe function is wrong.

The result for the parameters 1000, 1000 is incorrect.
It is due to res*(tem*tem)%MOD. This doesn’t work the way you expect it to and it overflows.

First it computes res*(tem*tem) and then it mods.
As all the terms can be upto 10^9+6, this will overflow.

Replacing res*(tem*tem)%MOD with res*((tem*tem)%MOD) is accpeted

The powe function is actually modular exponentiation. @rupinderg00 just made a silly mistake. :slightly_frowning_face:

Can someone tell the error please?
FastReader in=new FastReader();
int t=in.nextInt();
int n=in.nextInt();
long a=in.nextLong();
long p[]=new long[n];
long sum=a;
p[0]=a;long h=1;
for(int i=1;i<n;i++){
Not getting it???