Просто переберём все числа на отрезке $$$[l;r]$$$ и с помощью деления чисел на 2, 3, 5 проверить, является ли полученное число единицей. Асимптотика этого решения будет $$$n * \sigma(n)$$$, где $$$\sigma(n)$$$ — количество двоек, троек и пятёрок в факторизации числа.

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

bool f(int n){
    while((n & 1) == 0)
        n >>= 1;
    while(n % 3 == 0)
         n /= 3;
    while(n % 5 == 0)
        n /= 5;
    return n == 1;
}

int32_t main() {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    for(int i = l; i <= r; i++)
        cnt += f(i);
    cout << cnt;
}

Первая группа тестов:

Напишем перебор. Будем для каждого целого числа $$$x$$$ от $$$l$$$ до $$$r$$$ проверять его на простоту за O($$$\sqrt{x}$$$). Тогда итоговая асимптотика будет O($$$r \sqrt{r}$$$).

Вторая группа тестов:

1. Напишем обыкновенное решето Эратосфена за O($$$n \log n$$$) или за O($$$n \log \log n$$$) в зависимости от реализации.

2. Запустим перебор каждого числа от $$$l$$$ до $$$r$$$. Будем проверять числа на простоту эффективными методами, например вероятностным тестом Ферма за O($$$\log n$$$). Получаем асимптотику O($$$n \log n$$$)

Полное решение:

Напишем решето Эратосфена за O($$$n$$$)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e8;
 
int lp[N + 1];
int pref[N + 1];
int pr[N / 10 + 1];
int r = 0;
 
void precalc(int n) {
    for (int i=2; i<=n; ++i) {
        pref[i] += pref[i - 1];
        if (lp[i] == 0) {
            pref[i]++;
            lp[i] = i;
            pr[r] = i;
            r++;
        }
        for (int j = 0; j < r && pr[j] <= lp[i] && i * pr[j] <= n; ++j)
            lp[i * pr[j]] = pr[j];
    }
}
 
int32_t main(){
    int32_t l, r;
    cin >> l >> r;
    precalc(r);
    cout << pref[r] - pref[l];
}

Давайте научимся узнавать для заданной перестановки, сколько существует перестановок, лексикографически меньших заданной.

Давайте переберём перестановку. Предположим, что мы зафиксировали какой-то элемент $$$p_i$$$, тогда переберём все числа, меньшие $$$p_i$$$, но не использовавшиеся раньше. Правее них мы можем ставить любые числа по определению лексикографически меньшей перестановки.

Количество вариантов для каждого такого числа, меньшего $$$p_i$$$, будет равняться количеству перестановок, то есть $$$(n - i)!$$$ ( в 1-индексации). Асимптотика решения равна $$$O(n^2)$$$.

Используя дерево отрезков или дерево Фенвика можно получить асимптотику $$$O(n \log n)$$$

Зная количество перестановок, лексикографически меньших, мы можем найти номер текущей перестановки, прибавив 1.

#include <bits/stdc++.h>
using namespace std;

long long mod=1000000007;
long long n, fact[100005], perm;
long long fenw[1<<20];

void update(int x){
	while (x!=1<<20){
		fenw[x]++;
		x+=x&-x;
	}
}

long long query(int poz){
	long long ret=0;
	while (poz){
		ret+=fenw[poz];
		poz-=poz&-poz;
	}
	return ret;
}

int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
fact[1]=1;
for (int i=2; i<=n; i++)
	fact[i]=(fact[i-1]*i)%mod;
long long ans=1;
for (int i=1; i<=n; i++){
	cin >> perm;
	long long prev = perm-1-query(perm);
	update(perm);
	ans = (ans + (prev*fact[n-i])%mod)%mod;
} 
cout << ans << endl;
return 0;
}

Задача аналогична предыдущей. Будем восстанавливать сочетание слева направо. Переберём возможные значения текущего элемента и проверим, сколько сочетаний текущий элемент порождает. В зависимости от этого числа или ищем элемент дальше и отнимает полученное число сочетаний, или фиксируем этот элемент и переходим к поиску следующего. Асимптотика — O($$$k^2$$$).

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

int c[100][100];

void precalc(){
    for(int i = 0; i <= 32; i++)
        c[i][0] = 1;
    for(int i = 1; i <= 32; i++)
        for(int j = 1; j <= 32; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}

int32_t main() {
    precalc();
    int n, k, p;
    cin >> n >> k >> p;
    int prev = -1;
    for(int i = 0; i < k; i++){
        for(int j = max(prev + 1, (int)1); j <= n; j++){
            if(p < c[n - j][k - i - 1]){
                prev = j;
                cout << j << ' ';
                break;
            }
            else
                p -= c[n - j][k - i - 1];
        }
    }
}

Первые две группы тестов:

Напишем переборное решение. Просто удаляем ребро из графа для первого запроса, для второго запроса запустим DFS. Итоговая асимптотика — O($$$n^2$$$).

Будем обрабатывать запросы с конца. Тогда у нас есть пустой граф и два вида запросов: merge и ask. На такие запросы умеет отвечать такая структура данных, как СНМ(DSU). Асимптотика — O($$$n \cdot \alpha(n)$$$), где $$$\alpha(n)$$$ можно считать равным 5.

#include <bits/stdc++.h>

using namespace std;


int p[100000];
int rk[100000];

void init_dsu() {
    for (int i = 0; i < 100000; i++) {
        p[i] = i;
        rk[i] = 1;
    }
}

int get_root(int v) {
    if (p[v] == v) {
        return v;
    } else {
        return p[v] = get_root(p[v]);
    }
}

bool merge(int a, int b) {
    int ra = get_root(a), rb = get_root(b);

    if (ra == rb) {
        return false;
    } else {
        if (rk[ra] < rk[rb]) {
            p[ra] = rb;
        } else if (rk[rb] < rk[ra]) {
            p[rb] = ra;
        } else {
            p[ra] = rb;
            rk[rb]++;
        }

        return true;
    }
}

int32_t main() {
    cout.setf(ios::fixed);
    cout.precision(9);
    ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    init_dsu();
    while (m--){
        int u, v;
        cin >> u >> v;
    }
    vector<pair<string, pair<int, int>>> q;
    while(k--){
        string s;
        int u, v;
        cin >> s >> u >> v;
        q.emplace_back(s, make_pair(u, v));
    }
    stack<bool> st;
    while(!q.empty()){
        string s = q.back().first;
        int u = q.back().second.first, v = q.back().second.second;
        q.pop_back();
        if(s == "1")
            merge(u, v);
        else
            st.push(get_root(u) == get_root(v));
    }
    while(!st.empty()){
        cout << (st.top() ? "YES\n" : "NO\n");
        st.pop();
    }
}

В задаче требуется найти в массиве четыре таких различных числа a, b, c, d, что $$$a \oplus b \oplus c \oplus d = 0$$$. Переформулируем: $$$a \oplus b = c \oplus d$$$. Пусть k = $$$a \oplus b$$$. Сколько различных значений может принимать k? Самый старший бит $$$10^6$$$ это 16, а $$$2^{17}$$$ — 1 это 131071 — максимальное число, которое можно получить с помощью $$$a \oplus b$$$. Получаем 131072 различных значений $$$a \oplus b$$$. В массиве из n различных элементов, есть $$$\frac{n \cdot (n - 1)}{2}$$$ различных пар, а значит столько же ксоров двух чисел. Решив $$$\frac{n \cdot (n - 1)}{2}$$$ = 131072 и округлив ответ в большую сторону, получаем верхнюю оценку на n — 513. Значит, если размер массива больше или равен 513, то ответ точно Yes. Иначе решаем перебором за $$$n^2$$$.

#pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse", "sse2", "sse3", "sse4")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define orset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define hti cc_hash_table<int, int, hash<int>>
#define htp cc_hash_table<int, pii, hash<int>>
// #define double long double
// #define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define x first
#define y second
#define all(a) (a.begin()), (a.end())
#define gsz(x) ((int)x.size())
#define mat vector<vector<int>>
#define endl "\n"
#define LOCAL
#ifdef LOCAL
#define dbg(x) cerr << #x << ":" << (x) << endl
#define print(x) cerr << (x) << endl
#else
#define dbg(x) 0
#define print(x) 0
#endif

using namespace std;
using namespace __gnu_pbds;

const int N = 1e6 + 10;
const int B = 300;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int n;
int a[N];
bool was[N];

int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cout.precision(10);

    cin >> n;

    for(int i = 0; i < n; ++i)
    	cin >> a[i];

    if(n >= 513)
    {
    	cout << "Yes" << endl;
    	return 0;
    }

    for(int i = 0; i < n; ++i)
    	for(int j = i + 1; j < n; ++j)
    		if(was[a[i] ^ a[j]])
    		{
    			cout << "Yes" << endl;
    			return 0;
    		}
    		else
    			was[a[i] ^ a[j]] = true;

    cout << "No" << endl;
}

// n * (n - 1) / 2 = 131072
// n * (n - 1) = 262144
// n^2 - n - 262144 = 0
// d = 1048577
// n = (1 + 1025) / 2 = 513

Давайте добавим дополнительную вершину n + 1, которую мысленно соединим со всеми остальными вершинами. Стоимость каждого полученного ребра $$$(u, n + 1)$$$ будет $$$c_u$$$. Теперь построим MST(Мин остов) по такому графу. Это и будет ответ. Восстанавливать ответ тоже достаточно просто: из тех вершин, из которых MST провёл рёбра в дополнительную вершину, будет электростанция. Асимптотика — O($$$m \log n$$$).

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

struct point{
    int x, y;
};

int32_t main() {
    cout.setf(ios::fixed);
    cout.precision(9);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int g[n + 1][n + 1];
    point a[n];
    for(auto &i: a)
        cin >> i.x >> i.y;
    g[n][n] = 0;
    for(int i = 0; i < n; i++){
        cin >> g[n][i];
        g[i][n] = g[n][i];
    }
    int k[n];
    for(auto &i: k)
        cin >> i;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            g[i][j] = g[j][i] = (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y)) * (k[i] + k[j]);
    bool used[n + 1];
    memset(used, false, sizeof used);
    int min_e[n + 1];
    for(int i = 0; i <= n; i++)
        min_e[i] = LLONG_MAX;
    int sel_e[n + 1];
    memset(sel_e, -1, sizeof sel_e);
    min_e[0] = 0;
    vector<pair<int, int>> ans;
    for (int i=0; i<=n; ++i) {
        int v = -1;
        for (int j=0; j<=n; ++j)
            if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
                v = j;
        used[v] = true;
        if (sel_e[v] != -1)
            ans.emplace_back(v, sel_e[v]);
        for (int to=0; to<=n; ++to)
            if (!used[to] && v != to && g[v][to] < min_e[to]) {
                min_e[to] = g[v][to];
                sel_e[to] = v;
            }
    }
    int w = 0;
    for(auto i: min_e)
        w += i;
    cout << w << '\n';
    vector<int> f;
    vector<pair<int, int>> s;
    for(auto i: ans) {
        if (i.first == n || i.second == n)
            f.emplace_back(i.first == n ? i.second : i.first);
        else
            s.push_back(i);
    }
    cout << f.size() << '\n';
    for(auto i: f)
        cout << i + 1 << ' ';
    cout << '\n';
    cout << s.size() << '\n';
    for(auto i: s)
        cout << i.first + 1 << ' ' << i.second + 1 << '\n';
}

1, 2 и (3, если написать аккуратно) группа тестов:

1 вариант. Будем добавлять элементы в сет, а на запрос второго вида пройдёмся по сету и посчитаем то, что нас просят. Асимптотика — O($$$n^2$$$).

2 вариант. Будем добавлять элементы в сортированный вектор и поддерживать для него префиксные суммы. Таким образом, асимптотика будет O($$$n \cdot (n + \log n)$$$)

Полное решение:

Нам нужна такая структура данных, которая умеет быстро добавлять элементы и узнавать требуемую сумму. Для данной задачи можно построить декартово дерево, которое может добавлять элементы. Так же будем хранить в вершине дерева сумму на поддереве. Мы можем создать декартово дерево, которое будет поддеревом исходного, которое будет хранить все ключи от $$$l$$$ до $$$r$$$, с помощью операции split. А теперь сумма в корне это и будет требуемая сумма. Главное не забыть в конце объединить декартовы деревья в исходное. Асимптотика — O($$$n \log n$$$)

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> rnd(1, 100000000);

struct node{
    int key, pr;
    node *left, *right;
    int sz, sum;
    node(int k){
        sz = 1;
        key = sum = k;
        pr = rnd(gen);
        left = right = nullptr;
    }
};

int getsize(node* T){
    return T ? T->sz : 0;
}

int getsum(node* T){
    return T ? T->sum : 0;
}

void calc(node* &T){
    if(!T)
        return;
    T->sz = getsize(T->left) + getsize(T->right) + 1;
    T->sum = getsum(T->left) + getsum(T->right) + T->key;
}

pair<node*, node*> split(node* T, int k){
    if(T == nullptr)
        return {nullptr, nullptr};
    else if(T->key <= k){
        auto [T1, T2] = split(T->right, k);
        T->right = T1;
        calc(T);
        return {T, T2};
    }
    else{
        auto [T1, T2] = split(T->left, k);
        T->left = T2;
        calc(T);
        return {T1, T};
    }
}
node* merge(node* T1, node* T2){
    if(!T1)
        return T2;
    if(!T2)
        return T1;
    if(T1->pr > T2->pr){
        T1->right = merge(T1->right, T2);
        calc(T1);
        return T1;
    }
    else{
        T2->left = merge(T1, T2->left);
        calc(T2);
        return T2;
    }
}

bool find(node* T, int k){
    while(T) {
        if (T->key == k)
            return true;
        if(T->key > k)
            T = T->left;
        else
            T = T->right;
    }
    return false;
}
node* insert(node* T, int k){
    if(T == nullptr){
        T = new node(k);
        return T;
    }
    if(find(T, k))
        return T;
    auto [T1, T2] = split(T, k);
    T = merge(merge(T1, new node(k)), T2);
    return T;
}

int sum(node* &T, int l, int r){
    auto [T1, T2] = split(T, l - 1);
    auto [Tl, Tr] = split(T2, r);
    int sum = getsum(Tl);
    T = merge(merge(T1, Tl), Tr);
    return sum;
}

node* root = nullptr;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int sm = 0;
    while(n--){
        string s;
        cin >> s;
        if(s == "+"){
            int x;
            cin >> x;
            root = insert(root, (x + sm) % 1000000000);
            sm = 0;
        }
        else{
            int l, r;
            cin >> l >> r;
            sm = sum(root, l, r);
            cout << sm << '\n';
        }
    }
}

• Перебор:

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

• Динамическое программирование 1:

Создадим dp [n][5], что будет означать количество способов сделать очередь длины $$$n$$$, оканчивающуюся на 1, 2, 3, 4, 5 соответственно: dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = 1. Далее довольно простой переход: просто идём туда, куда можем по условию (суммируем значения тех вариантов, откуда могли прийти). Ответом будет сумма по последнему слою ДП.

• Динамическое программирование 2:

Просто будем хранить только последние два слоя ДП.

• Динамическое программирование 3, полное решение:

Представим себе матрицу 5х5, где все ячейки, кроме (3, 4), (3, 5), (5, 4), (5, 5), которые будут нулями, будут единицами, что будет означать возможность существования такой пары. Также изначально у нас есть один вариант для каждого варианта набора, заканчивающегося на патрон силой от 1 до 5 составить очередь длины 1 — взять соответствующий патрон. Тогда у нас есть ещё одна матрица 1x5, заполненная единицами — количество изначальных способов. Если если умножить вторую матрицу на первую, возведённую в степень $$$n-1$$$, то сумма элементов в первой строке полученной матрицы и будет искомым ответом, т. к. мы фактически находим количество для каждого варианта очереди, заканчивающегося на патрон силой от 1 до 5 составить очередь длины $$$n$$$.

#include <bits/stdc++.h>

#define int int64_t
#define double long double

using namespace std;

const int mod = 999999937;

vector<vector<int>> f;
vector<vector<int> > x;
vector<vector<int> > matrix;

vector<vector<int>> mult(vector<vector<int>> a, vector<vector<int>> b) {
    int m = a.size(), n = b.size(), k = b[0].size();
    vector<vector<int>> p(m, vector<int>(k));
    for(int i = 0; i < m; i++)
        for(int j = 0; j < k; j++)
            for(int l = 0; l < n; l++)
                p[i][j] = (p[i][j] + a[i][l] * b[l][j]) % mod;
    return p;
}

vector<vector<int> > binpow(vector<vector<int> > v, int y){
    if(y == 1)
        return v;
    if(y & 1)
        return mult(binpow(v, y - 1), v);
    vector<vector<int>> cur = binpow(v, y>>1);
    return mult(cur, cur);
}

int32_t main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if (n == 1) {
        cout << 5 << '\n';
        return 0;
    }
    f.assign(1, vector<int>(5, 1));
    matrix.assign(5, vector<int>(5, 1));
    matrix[2][3] = matrix[2][4] = matrix[4][3] = matrix[4][4] = 0;
    x = binpow(matrix, n - 1);
    f = mult(f, x);
    int sum = 0;
    for (auto i: f[0]) {
        sum += i;
        if (sum >= mod)
            sum %= mod;
    }
    cout << sum << '\n';
}

Для первой группы тестов достаточно написать простой перебор за O($$$n^3$$$): добавим каждую подстроку в set и затем выведем размер сета.

Для второй группы можно написать тот же перебор, но с сохранением текущей строки и добавлением туда с перебором правой границы по одному символу. O($$$n^2$$$)

Для третьей группы тестов построим по строке суффиксный массив и насчитаем для него lcp (наибольший обший префикс). Теперь мы фактически просто берём очередной в порядке сортировки суффикс и смотрим, какие его префиксы дают новые подстроки. Текущий суффикс $$$p_i$$$ (где $$$p$$$ — суффиксный массив) даст в качестве новых подстрок все свои префиксы, кроме совпадающих с префиксами суффикса $$$p_{i-1}$$$. Т.е. все его префиксы, кроме $$$lcp_{i-1}$$$ первых, дадут новые подстроки. Тогда ответ на задачу будет $$$\sum_{i = 0}^{n - 1}(n - p_i) - \sum_{i = 0}^{n - 1}lcp_i$$$. Асимптотика — O($$$n \log n$$$).

Также можно решить эту задачу суффиксным деревом или префикс-функцией. Асимптотика — O($$$n$$$)

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

int sum_mod(int x, int y, int mod){
    x += y;
    if(x >= mod)
        x -= mod;
    return x;
}

void sort_cc_sh(string &s, vector<int> &sa) {
    int n = s.size();
    vector<int> a, na;
    vector<int> color, ncolor;
    vector<int> buckets;
    buckets.assign(256, 0);
    for (char c: s)
        buckets[c]++;
    for (int i = 1; i < 256; i++)
        buckets[i] += buckets[i - 1];
    a.assign(n, -1);
    for (int i = n - 1; i >= 0; i--)
        a[--buckets[s[i]]] = i;
    color.assign(n, 0);
    color[a[0]] = 0;
    for (int i = 1; i < n; i++)
        if (s[a[i]] != s[a[i - 1]])
            color[a[i]] = color[a[i - 1]] + 1;
        else
            color[a[i]] = color[a[i - 1]];
    na.assign(n, -1);
    ncolor.assign(n, -1);
    for (int l = 1; l < n; l <<= 1) {
        buckets.assign(n, 0);
        for (int i = 0; i < n; i++)
            buckets[color[i]]++;
        for (int i = 1; i < n; i++)
            buckets[i] += buckets[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            int j = a[i] - l;
            if (j < 0)
                j += n;
            na[--buckets[color[j]]] = j;
        }
        a.swap(na);
        ncolor[a[0]] = 0;
        for (int i = 1; i < n; i++)
            if (color[a[i]] == color[a[i - 1]] && color[sum_mod(a[i], l, n)] == color[sum_mod(a[i - 1], l, n)])
                ncolor[a[i]] = ncolor[a[i - 1]];
            else
                ncolor[a[i]] = ncolor[a[i - 1]] + 1;
        color.swap(ncolor);
    }
    sa = a;
}

void build_suf_array(string &s, vector<int> &sa){
    s.push_back((char)0);
    sort_cc_sh(s, sa);
    s.pop_back();
    sa.erase(sa.begin());
}

void build_lcp(string &s, vector<int> &sa, vector<int> &lcp){
    int n = s.size();
    lcp.assign(n - 1, -1);
    vector<int> pos(n);
    for(int i = 0; i < n; i++)
        pos[sa[i]] = i;
    int k = 0;
    for(int i = 0; i < n; i++){
        if(k > 0)
            k--;
        if(pos[i] == n - 1)
            k = 0;
        else{
            int j = sa[pos[i] + 1];
            while (max(i + k, j + k) < n && s[i + k] == s[j + k])
                k++;
            lcp[pos[i]] = k;
        }
    }
}

int32_t main() {
    string s;
    cin >> s;
    vector<int> sa;
    build_suf_array(s, sa);
    vector<int> lcp;
    build_lcp(s, sa, lcp);
    int sum = 0;
    for(auto i : sa)
        sum += s.size() - i;
    for(auto i: lcp)
        sum -= i;
    cout << sum;
}