### OK — I GOT -20 , IGNORE THIS FUCK THIS LIFE↵
↵
**Hi ^~^**↵
↵
#### Part One [Useful Functiones]:↵
↵
↵
**1.1 — power-Function:**↵
↵
**[Binary Exponentiation]**↵
is a trick which allows to calculate $a^n$ using $O(\log n) $↵
↵
The idea is that we can traverse through all the bits of a number from LSB to MSB in $O(\log n) $ time.↵
↵
Write $n$ in base $2$.↵
↵
The number has exactly $ \lfloor \log_2 n \rfloor + 1 $ digits in base 2, we only need to perform ↵
$O(\log n) $ multiplications, if we know the powers $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log n \rfloor}}$ .↵
↵
<spoiler summary="Implementation">↵
↵
```c++ ↵
int dnt_pow(int a, int b, int md = mod)↵
{↵
int pw_ans = 1; ↵
while(b)↵
{↵
if(b&1)↵
{↵
pw_ans = (a*pw_ans)%md;↵
}↵
a = (a*a)%md;↵
b >>= 1;↵
}↵
return pw_ans ;↵
}↵
```↵
</spoiler>↵
↵
**1.2 — GCD-Function:**↵
↵
**[Euclidean algorithm]**↵
is a trick which allows to calculate $gcd(a,b) $ using $O(\log \min(a, b))$↵
The idea is that subtract the smaller number from the larger one until one of the numbers is zero.↵
↵
For Time Complexity and Binary GCD you can read [This](https://cp-algorithms.com/algebra/euclid-algorithm.html).↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
int dnt_gcd(int a, int b) ↵
{↵
return b ? gcd(b,a%b):a ;↵
} ↵
↵
```↵
</spoiler>↵
↵
↵
**Note that you can calculate $lcm(a,b)$ with $\frac{a}{gcd(a,b)}\ * b $** ↵
↵
↵
**1.3 — Factorial & nCr & ...:**↵
↵
Sometimes you need to calculate $\binom n k $↵
↵
For that first we precompute all factorials modulo $ mod $ with $O(N)$.↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
void dnt_bld()↵
{↵
fac[0] = 1;↵
for(int i = 1 ; i < N ; i++) ↵
{↵
fac[i] = (fac[i-1] * i) % mod;↵
}↵
}↵
int dnt_ncr(int n,int r)↵
{↵
return fac[n] * inverse(fac[r] * fac[n - r] % mpd) % mod;↵
}↵
```↵
</spoiler>↵
↵
**BUT WE CAN PRECOMPUTE INVERSE OF FAC[I] IN $ O(Nlogmod) $**↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
void dnt_bld()↵
{↵
fac[0] = 1;↵
inv[0] = dnt_pow(fac[0],mod-2);↵
for(int i = 1 ; i < N ; i++) ↵
{↵
fac[i] = (fac[i-1] * i) % mod;↵
inv[i] = dnt_pow( fac[i] , mod-2);↵
}↵
}↵
int dnt_ncr(int n,int r)↵
{↵
return fac[n] * inv[r] % mod * inv[n-r] % mod;↵
}↵
```↵
</spoiler>↵
↵
↵
**1.4 Fibonacci in 20 line:**↵
↵
as you know you can calculate $n-th$ Fibonacci number with matrix.↵
↵
<spoiler summary="here">↵
↵
</spoiler>↵
↵
it can be proved that : ↵
↵
```c++↵
F[2*n — 1] = F[n]*F[n] + F[n — 1]^2↵
↵
F[2*n] = (F[n — 1] + F[n + 1])*F[n] = (2*F[n — 1] + F[n])*F[n]↵
```↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
map<long, long> fib;↵
int dnt_fib(int n) ↵
{↵
if (fib.count(n)) return fib[n];↵
if (n % 2 == 0) ↵
{↵
return fib[n] = ( dnt_fib(n/2)*dnt_fib(n/2) + dnt_fib(n/2-1)*dnt_fib(n/2-1) ) % mod;↵
} ↵
else ↵
{↵
return fib[n] = ( dnt_fib(n/2 + 1) * dnt_fib(n/2) + dnt_fib(n/2 - 1) * dnt_fib(n/2) ) % mod;↵
}↵
}↵
int solve()↵
{↵
fib[0] = 1;↵
fib[1] = 1;↵
int n;↵
cin >> n;↵
cout << (n==0 ? 0 : dnt_fib(n-1)) << endl;↵
↵
}↵
```↵
</spoiler>↵
↵
tnx [user:kien_coi_1997,2023-10-08] and [user:i_love_tigersugar,2023-10-08]↵
↵
↵
↵
**1.5 Built-in useful function:**↵
↵
```c++↵
vector<int> a(n);↵
↵
iota(a.begin(), a.end(), 1);↵
// a = 123..↵
↵
random_shuffle(a.begin(), a.end());↵
// a = random permutation of a↵
↵
vector<int> ps(n);↵
partial_sum(a.begin(), a.end(), ps.begin());↵
// ps[i] = a[0] + a[1] + .... a[i-1] + a[i] ( ps[i] = ps[i-1] + a[i])↵
↵
vector<int> h(n);↵
adjacent_difference(a.begin(), a.end(), h.begin());↵
// h[0] = a[0]↵
// (i>0) h[i] = = a[i] - a[i-1]↵
↵
cout << accumulate(a.begin(), a.end(), x) ;↵
//cout x + a[0] + a[1] + a[2] + ... + a[n]↵
↵
cout << inner_product(a.begin(), a.end(), b.begin(), 234) << "\n";↵
// x = 234 + sum(a[i] * b[i])↵
```↵
tnx [user:Igorjan94,2023-10-08] for this↵
↵
↵
Was this blog helpful?
↵
**Hi ^~^**↵
↵
#### Part One [Useful Functiones]:↵
↵
↵
**1.1 — power-Function:**↵
↵
**[Binary Exponentiation]**↵
is a trick which allows to calculate $a^n$ using $O(\log n) $↵
↵
The idea is that we can traverse through all the bits of a number from LSB to MSB in $O(\log n) $ time.↵
↵
Write $n$ in base $2$.↵
↵
The number has exactly $ \lfloor \log_2 n \rfloor + 1 $ digits in base 2, we only need to perform ↵
$O(\log n) $ multiplications, if we know the powers $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log n \rfloor}}$ .↵
↵
<spoiler summary="Implementation">↵
↵
```c++ ↵
int dnt_pow(int a, int b, int md = mod)↵
{↵
int pw_ans = 1; ↵
while(b)↵
{↵
if(b&1)↵
{↵
pw_ans = (a*pw_ans)%md;↵
}↵
a = (a*a)%md;↵
b >>= 1;↵
}↵
return pw_ans ;↵
}↵
```↵
</spoiler>↵
↵
**1.2 — GCD-Function:**↵
↵
**[Euclidean algorithm]**↵
is a trick which allows to calculate $gcd(a,b) $ using $O(\log \min(a, b))$↵
The idea is that subtract the smaller number from the larger one until one of the numbers is zero.↵
↵
For Time Complexity and Binary GCD you can read [This](https://cp-algorithms.com/algebra/euclid-algorithm.html).↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
int dnt_gcd(int a, int b) ↵
{↵
return b ? gcd(b,a%b):a ;↵
} ↵
↵
```↵
</spoiler>↵
↵
↵
**Note that you can calculate $lcm(a,b)$ with $\frac{a}{gcd(a,b)}\ * b $** ↵
↵
↵
**1.3 — Factorial & nCr & ...:**↵
↵
Sometimes you need to calculate $\binom n k $↵
↵
For that first we precompute all factorials modulo $ mod $ with $O(N)$.↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
void dnt_bld()↵
{↵
fac[0] = 1;↵
for(int i = 1 ; i < N ; i++) ↵
{↵
fac[i] = (fac[i-1] * i) % mod;↵
}↵
}↵
int dnt_ncr(int n,int r)↵
{↵
return fac[n] * inverse(fac[r] * fac[n - r] % mpd) % mod;↵
}↵
```↵
</spoiler>↵
↵
**BUT WE CAN PRECOMPUTE INVERSE OF FAC[I] IN $ O(Nlogmod) $**↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
void dnt_bld()↵
{↵
fac[0] = 1;↵
inv[0] = dnt_pow(fac[0],mod-2);↵
for(int i = 1 ; i < N ; i++) ↵
{↵
fac[i] = (fac[i-1] * i) % mod;↵
inv[i] = dnt_pow( fac[i] , mod-2);↵
}↵
}↵
int dnt_ncr(int n,int r)↵
{↵
return fac[n] * inv[r] % mod * inv[n-r] % mod;↵
}↵
```↵
</spoiler>↵
↵
↵
**1.4 Fibonacci in 20 line:**↵
↵
as you know you can calculate $n-th$ Fibonacci number with matrix.↵
↵
<spoiler summary="here">↵
↵
</spoiler>↵
↵
it can be proved that : ↵
↵
```c++↵
F[2*n — 1] = F[n]*F[n] + F[n — 1]^2↵
↵
F[2*n] = (F[n — 1] + F[n + 1])*F[n] = (2*F[n — 1] + F[n])*F[n]↵
```↵
↵
<spoiler summary="Implementation">↵
```c++ ↵
map<long, long> fib;↵
int dnt_fib(int n) ↵
{↵
if (fib.count(n)) return fib[n];↵
if (n % 2 == 0) ↵
{↵
return fib[n] = ( dnt_fib(n/2)*dnt_fib(n/2) + dnt_fib(n/2-1)*dnt_fib(n/2-1) ) % mod;↵
} ↵
else ↵
{↵
return fib[n] = ( dnt_fib(n/2 + 1) * dnt_fib(n/2) + dnt_fib(n/2 - 1) * dnt_fib(n/2) ) % mod;↵
}↵
}↵
int solve()↵
{↵
fib[0] = 1;↵
fib[1] = 1;↵
int n;↵
cin >> n;↵
cout << (n==0 ? 0 : dnt_fib(n-1)) << endl;↵
↵
}↵
```↵
</spoiler>↵
↵
tnx [user:kien_coi_1997,2023-10-08] and [user:i_love_tigersugar,2023-10-08]↵
↵
↵
↵
**1.5 Built-in useful function:**↵
↵
```c++↵
vector<int> a(n);↵
↵
iota(a.begin(), a.end(), 1);↵
// a = 123..↵
↵
random_shuffle(a.begin(), a.end());↵
// a = random permutation of a↵
↵
vector<int> ps(n);↵
partial_sum(a.begin(), a.end(), ps.begin());↵
// ps[i] = a[0] + a[1] + .... a[i-1] + a[i] ( ps[i] = ps[i-1] + a[i])↵
↵
vector<int> h(n);↵
adjacent_difference(a.begin(), a.end(), h.begin());↵
// h[0] = a[0]↵
// (i>0) h[i] = = a[i] - a[i-1]↵
↵
cout << accumulate(a.begin(), a.end(), x) ;↵
//cout x + a[0] + a[1] + a[2] + ... + a[n]↵
↵
cout << inner_product(a.begin(), a.end(), b.begin(), 234) << "\n";↵
// x = 234 + sum(a[i] * b[i])↵
```↵
tnx [user:Igorjan94,2023-10-08] for this↵
↵
↵
Was this blog helpful?
