https://www.codechef.com/viewsolution/24881704

Performed several optimisations but couldn’t manage to get AC.

Any kind of help is appreciated.

https://www.codechef.com/viewsolution/24881704

Performed several optimisations but couldn’t manage to get AC.

Any kind of help is appreciated.

Try running ur query block in Qlog(N) without using lower/upper_bound, it’s easy to think

2 Likes

First few things I can see:

- Change
`ll mul(ll x,ll y)`

to`inline ll mul(ll x,ll y)`

- Remove the redundant if statement in
`mul`

- Precompute factorials and their inverses more efficiently and also precompute modular inverses for each element.

My code for this:

```
fact[0] = 1;
for( int i=1; i<=n; ++i )
fact[i] = 1ll*i*fact[i-1] %m;
ifac[n] = power(fact[n], m-2);
for( int i=n; i>0; --i )
ifac[i-1] = 1ll*i*ifac[i] %m;
for( int i=1; i<=n; ++i )
modinv[i] = 1ll*ifac[i]*fact[i-1] %m;
```

I will edit this if I see more.

1 Like

Thanks, will try to remove lower/upper bound and precompute them.

Thanks, will optimise that.