Алгоритм МО

Рассмотрим такую задачу
Дано много-много запросов, состоящий из границ отрезка и числа x
Вам нужно для каждого отрезка ответить на вопрос: Сколько чисел, лежащий в нашем отрезке равны x?

Решение:
Воспользуемся Алгоритмом МО

Для начала, чтобы все работало намного быстрее, чем сейчас - сожмем числа
То есть:
Пусть есть массив [1, 5, 3, 6, 1, 6] -> [1, 2, 3, 4, 1, 4]

Воспользуемся идеей из прошлой задачи и разобьем отрезки в блоки по левой границе. Внутри блока отсортируем их по правой границе

Дальше, внутри каждого нового блока посчитаем ответ в тупую для первого отрезка

Дальше, для каждого блока будем двигать левые границы в тупую, а правую - только направо

Тогда суммарно наша правая граница пройдет максимум N элементов => работает за O(N)

Всего блоков √n => Суммарная асимптотика O(n√n)

Военная хитрость:

Нечетные блоки отсортируем по возрастанию, четные - по убыванию (это будет работать быстрее)

лол

Оптимизация какого-то что?

жесть там какие-то тяжелые и легкие вершины, но задача изи короче мне пофиг

Префикс Функция

Префикс функцией от строки S называется такой массив p, где Pi - это длина наибольшего префикса длинны S, который также является суффиксом i-того префикса (не считая весь i-й префикс)

Например, для строки "aataataa" префикс функция будет равна [0,1,0,1,2,3,4,5]

Код:

int n;
str s;
vector<int> p(n);
for(int i = 1; i < n; i++){
    int tmp = p[i - 1]
    while(s[i] != s[tmp] && tmp){
        tmp = s[tmp - 1]
    }
    if(s[i] == s[tmp]){
        p[i] = tmp + 1;
    }
}

Манакер

Пусть у нас есть строка S и мы хотим в ней найти все подпалиндромы

https://ru.algorithmica.org/cs/string-searching/manacher/ - тут

Бор

Бор — это структура данных для компактного хранения строк

Вопросы, на которые вы должны сами отвечать

1. Что считаем?
2. Как считаем?
3. В каком порядке считаем?
4. Какие начальные значения?
5. Где ответ?

Гамильтонов путь

dp[last][mask] = min длина Гамильтонова пути из S в Last, если посетить вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
𝒪(2^n * n^2)

Начальные значения:
dp[s][1 << s] = 0, остальные - INF

Где ответ?
dp[i][полная маска]

Кол-во гамильтоновых путей из вершины S

dp[last][mask] = кол-во Гамильтоновых путей из S в last, если посетили вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
dp[s][1 << s] = 1
dp[next][mask | (1 << next)] += dp[last][mask]

Ответ?
SUM dp[i][(1 << n) - 1]

Введите текст

Есть числа 0...2^n - 1
a[0], a[1], .. a[2^n - 1]
Для каждой mask посчитать сумму:
SUM a[i], где i - подмаска нашей маски

Пример:
mask = 6 = 100
a[000] + a[010] + a[100] + a[110]

int n;
for(int mask = 0; mask < (1 << n); mask++){
    for(int submask = mask; submask > 0; submask=(submask - 1)&mask){
        ...
    }
}

dp[mask][i] - сумма a[submask], где биты 0...I в mask и subtask могут различаться, а остальные совпадают

dp[mask][0] = a[mask]
Если i-тый бит mask = 0, то dp[mask][i + 1] = dp[mask][i]
Иначе dp[mask][i + 1] = dp[mask][i] + dp[mask ^ (1 << i)][i]

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        dp[mask][i + 1] = dp[mask][i]
        if((mask >> i) & 1){
            dp[mask][i + 1] += dp[mask ^ (1 << i)][i]
        }
    }
}

Оптимизация: можно сделать dp - одномерным, тогда получим такой код:

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        if((mask >> i) & 1){
            dp[mask] += dp[mask ^ (1 << i)]
        }
    }
}

Работает столько же, но памяти намного меньше

пошли нафиг

https://wiki.algocode.ru/index.php?title=ДП_по_профилю

Двумерное Дерево Фенвика

Аналогично

Код (скорее всего с багами):

ll n;
vector<vector<ll>> f(MAXN, vector<ll>(MAXN));


ll get_sum(int i, int j){
    int r = 0;
    while(j > 0){
        int k = i;
        while(k > 0){
            r += f[k][j];
            k -= k & -k;
        }
        j = j & -j;
    }
    return r;
}


ll sum(int x1, int y1, int x2, int y2){
    return get_sum(x2, y2) - get_sum(x1, y2) - get_sum(x2, y1) + get_sum(x1, y1);
}

void add(int i, int j, int x){
    while(j <= n){
        int k = i;
        while(k <= n){
            f[k][j] += x;
            k += k & (~k);
        }
        j += j & (~j);
    }
}

Sparse Table

Sparse Table - структура данных, позволяющая находить минимум на отрезке

#define MAX 100010
#define LOGMAX 30

ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(MAX, vector<ll>(LOGMAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l + 1);
    if (Sparce[l][j] <= Sparce[r - (1 << j) + 1][j]) {
        return Sparce[l][j];
    }
    return Sparce[r - (1 << j) + 1][j];
}

...
в функции main 
for (ll i = 0; i < n; i++) {
    Sparce[i][0] = arr[i];
}
for (ll j = 1; (1 << j) <= n; j++) {
    for (ll i = 0; (i + (1 << j) - 1) < n; i++) {
        if (Sparce[i][j - 1] < Sparce[i + (1 << (j - 1))][j - 1]) {
            Sparce[i][j] = Sparce[i][j - 1];
        } else {
            Sparce[i][j] = Sparce[i + (1 << (j - 1))][j - 1];
        }
    }
}

Оптимизация:

#define MAX 100010
#define LOGMAX 30
ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(LOGMAX, vector<ll>(MAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l);
    return min(Sparce[j][l], Sparce[j][r - (1 << j)]);
}


int main() {
    for (ll i = 0; i < n; i++) {
        Sparce[0][i] = arr[i];
    }
    for (ll j = 0; j < LOGMAX - 1; j++) {
        for (ll i = 0; i + (2 << j) <= n; i++) {
            Sparce[j + 1][i] = min(Sparce[j][i], Sparce[j][i + (1 << j)]);
        }
    }
}

Disjoint Sparse Table

Sparse Table не мог быть построен для тех функций от подотрезка массива, для которых каждое число подотрезка должно быть учтено ровно один раз. Disjoint Sparse Table решает эту проблему и с предподсчётом за O(nlogn) позволяет в онлайне за O(1) находить почти любые функции от подотрезка, например кол-во минимумов, или произведение по непростому модулю. ~ wiki.algocode.ru

Основная идея: разделяй и властвуй

TODO: написать дальше, автор конспекта закрыл ноут и пошел внимательно слушать

Ссылки данной штуки: https://algorithmica.org/ru/sparse-table, https://wiki.algocode.ru/index.php?title=Disjoint_Sparse_Table

Факторизация за O(sqrtN)

Пусть у нас есть число N
Оно представимо в виде N = a * b. Заметим, что одно из чисел a и b <= sqrt(n) (иначе a * b > n) => можно перебирать делители N до его корны

Решето Эратосфена за O(NLogLogN)

//БУДЬТЕ АККУРАТНЕЙ С ПЕРЕПОЛНЕНИЕМ!!!
int n;
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
        }
    }
} 

Прикол с minDiv (чтобы факторизацию делать)

int n;
vector<int> minDiv(n);
vector<bool> isPrime(n);
for(int i = 2; i <= n; i++){
    isPrime[i] = true;
    minDiv[i] = i;
}
for(int i = 2; i * i <= n; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= n; j++){
            isPrime[j] = false;
            minDiv[j] = min(minDiv[j], i);
        }
    }
}

Диофантовы уравнения

Уравнения вида a*x + b*y = c (a, b, c - известны)

Прикол:
Если (a, b) = g, то существуют x и y такие, что a*x + b*y = g
(a, b) -> (b, a % b)
b * x1 + (a % b) * y1 = g
(Для тех, кто не знал - a % b = a - [a / b] * b)
b*x1 + (a - [a / b] * b) * y1 = a * y1 + b * (x1 - [a / b] * y1)
Пример шапки функции:

int gcd(int a, int b, int &x, int &y){
    ...
}

Заметим, что a * (x + b) + b (y - a) = a * x + b * y => x = x0 + t * b/g;
y = y0 - t * a/g

Теперь решим основную задачу
Воспользуемся тем, что мы умеем решать для НОДа и тупо домножим коэффициенты.
Если c % g == 0 => решений бесконечно много
Если c % g != 0 => решений нет

Функция Эйлера

ф(n) (да, это фи) - количество взаимнопростых чисел, которые меньше n
ф(10) = 4

Заметим тупые свойства:

1. ф(р) = р - 1
2. ф(р^n) = p^n - p^(n - 1)

Так же интересное свойство:
ф(a) * ф(b) = ф(a*b) для (a, b) = 1 (я не собираюсь это доказывать, так как а) это никому не нужно, б) это долго и скучно)

Тогда достаточно просто считается ф(n) для любого n
ф(n) = ф(p1^L1 * p2^L2 * p3^L3 * ... ) = ф(p1^L1) * ф(p2^L2) * ... = (тупое свойство 2) = n * (p1 - 1 / p1) * ... * (pK - 1 / pK)
(лучше считать через ans / p, ans *= (p - 1)

int n;
int ans = n;
for(int i = 2; i * i <= n; i++){
    if(n % i == 0){
        ans /= i;
        ans *= (i - 1);
        while(n % i == 0){
            n /= i;
        }
    }
}
if(n > 1){
    ans /= n;
    ans *= (n - 1);
}

Количество делителей числа

Пусть у нас n = p1^L1 + p2^L2 + p3^L3 + ... + pK^LK
Тогда, кол-во делителей = (L1 + 1) * (L2 + 2) * (L3 + 3) * ... * (LK + 1) (очевидно)

Малая Теорема Ферма

a^(p - 1) ≡ 1 (mod p) при (a, p) = 1

Теорема Эйлера

a^ф(n) ≡ 1 (mod m) при (a, m) = 1

Функции модульной арифметики

const int MOD = 998244353;


int add(int a, int b){
    if(a + b >= MOD){
        return a + b - MOD;
    }
    else{
        return a + b;
    }
}


int sub(int a, int b){
    if(a - b < 0){
        return a + b - MOD;
    }
    else{
        return a - b;
    }
}

Китайская теорема об остатках

TODO (сори, я не успел записать)

Мем с модулями

a * g ≡ b * g (mod m * g) -> a ≡ b (mod m)
a * g ≡ b * g (mod m) -> a ≡ b (mod m) при (m, g) = 1
a ≡ b (mod m) -> a + x ≡ b + x (mod m)

С из N по K

(n, k) = n! / (k! * (n - k)!)
n! = (n - 1)! * n

надеюсь я с комментариями нигде не напутал...

int n;
int f[n], rf[n];
for(int i = 1; i < n; i++){
    f[i] = mul(f[i - 1], i); //умножение чисел по модулю
}
rf[n - 1] = inv(f[n - 1]); //обратное число по модулю
for(int i = n - 2; i >= 0; i--){
    rf[i] = mul(rf[i + 1], i + 1); //умножение чисел по модулю
}

Мемы:
1/n = (n - 1)! / n!
N^-1 = f[N - 1] * rf[N] (mod M)

Задачка

Надо найти все простые числа на отрезке [L, R]
(R-L+1 < 1e7)

int l, r;
vector<int> primes; //предпосчитать
vector<bool> isPrime(r - l + 1, true);
for(auto &i : primes){
    for(int j = i * max((l + i - 1) / i, i); j <= r; j += i){
        isPrime[j - l] = false;
    }
}

Линейное решето Эратосфена

int n;
vector<int> minDiv(n);
vector<int> primes;
iota(minDiv.begin(), minDiv.end(), 0);
for(int i = 2; i < n; i++){
    if(minDiv[i] == i){
        primes.pb(i);
    }
    for(auto &p : primes){
        if(p > minDiv[i] || p * i >= n){
            break;
        }
        minDiv[p * i] = p;
    }
}