WA in DBFD

Anyone explain Why I am getting WA from 2 Test case. in DBFB OF MAY Long challenge.
I even checked for integer overflow in highest test case possible. in taking n,m=10e5,a[i]=10e9…I got 603392858. and from one correct solution also 603392858.

My solution

Correct solution

Try adding %mod here
F[0][0] = x%mod;
… for all four…
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;

I have done by your way still getting WA from another case.
new soltuon

And resubmitting exactly same soltion again i got error in other case.
Repeated solution.

Confusion!!

Hey @l_returns
could you please check my soln. also

what am i doing wrong with modulo operators??

Soln

@avik26091998 Yes… add modulo here
for(int i = 4; i <= 100001; ++i) pre_fib[i] = ((pre_fib[i - 1] + pre_fib[i - 2]));

as
for(int i = 4; i <= 100001; ++i) pre_fib[i] = ((pre_fib[i - 1] + pre_fib[i - 2])%MOD);

I am also getting wrong answer for my solution.

if anyone could tell me. Link : https://www.codechef.com/viewsolution/18586999

and even then problem still exist then and only then try checking this line for overflow…
cuz its too messy for me to understand… avoid multiplying three integers…
multiply like this ((a*b)%mod)*c)%mod…

res=(res + (((F[0][0]%mod)(sumb%mod))%mod + (((m%mod)((F[0][1]%mod)*(a[i]%mod)%mod)%mod)%mod)%mod)%mod)%mod;

I am still getting errors… according to modulus multiplication…

(ab)%mod=((a%mod)(b%mod))%mod. I also used the same

here is your passed solution :
https://www.codechef.com/viewsolution/18600970

problem was in modulos and brackets of matrix multiplication function and problem was in size of array B…

i would suggest you to not use too much modulos where they are not necessary and make your code unreadable and hard to debug…

see u wrote F[0][0]%mod and u already stored modulo value in F[0][0]… i mean F[0][0] was already < mod… then you should avoid that… it may give you tle in some questions… I have experienced that some ques give tle if u have lot of extra modulos…

Dammm I missed it because of modulus…Thank you very much for help

welcome :slight_smile:

@rishabhjha708 edit the question heading. It should be ‘DBFB’ not ‘DBFD’.