Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, watchmaker, Вы писали:

W>>Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю.

Б>Вычисление биномиальных коэффициентов "в лоб" для n=100000 не быстро даже если считать по модулю.


Теорема Люка говорит нам, что для посчёта биномиального коэффициента достаточно будет сложить log₃N чисел.
В задаче ограничение на число элементов L = 100000.
Одиннадцать операций сложения — это не очень долго. Даже наоборот, достаточно быстро.
(в формуле в вики там умножение, но практичнее складывать логарифмы; а впрочем можно и умножать, не сильно медленнее)

// предпосчитанная таблица C^k_n, n=0..2, k=0..2

// BIN3LOG2[n][k] ≈ log_2(C^k_n mod 3)
const unsigned BIN3LOG2[3][4] = {
    {0x00000000, 0xffff0000, 0xffff0000},
    {0x00000000, 0x00000000, 0xffff0000},
    {0x00000000, 0x00000001, 0x00000000},
};

// экспонента: 2^x mod 3
int pow2mod3(unsigned x) {
    return (x & 0xffff0000) ? 0 : 1 + (x & 1);
}

// вычисление C^k_n, где n, k записаны в троичной системе счисления
int b(const char nv[], const char kv[], const size_t l) {
    unsigned rl = 0;
    for (size_t i = 0; i < l; ++i) {
        rl += BIN3LOG2[nv[i]][kv[i]];
    }
    return pow2mod3(rl);
}

	остальное
	char solve(const string& l) { size_t n = l.size(); const std::vector<char> bc = binomial(n - 1); int r = 0; for (size_t i = 0; i < n; ++i) { r += l[i] * bc[i]; } r <<= ~n & 1; return "BRGBRG"[r % 3 + 3]; } Лень делать совсем уж быстро, поэтому функция подсчёта строки треугольника Паскаля сделана отдельно и с выделением памяти, а не inplace. Зато сразу видно, что в решении нет ничего кроме скалярного произведения и учёта чётности.   binomial Тут только одна содержательная строка, остальное — перевод в троичную систему счисления и инкремент в ней же std::vector<char> binomial(size_t n) { std::vector<char> r; r.reserve(n + 1); std::vector<char> nv; // n в троичной системе счисления for (size_t tn = n; tn; tn /= 3) { nv.push_back(tn % 3); } nv.push_back(0); std::vector<char> kv(nv.size(), 0); // k в троичной системе счисления for (size_t k = 0; k <= n; ++k) { r.push_back(b(nv.data(), kv.data(), nv.size() - 1)); for (size_t t = 0; ; t++) { if (kv[t] == 2) { kv[t] = 0; } else { kv[t] += 1; break; } } } return r; }

Кстати, fun fact: можно исходный вектор символов не приводить к 0,1,2, так как ascii-коды символов RGB уже имеют различные остатки от деления на 3. Сразу можно символы на биномиальные коэффициенты умножать

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, watchmaker, Вы писали:

W>>Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю.

Б>Вычисление биномиальных коэффициентов "в лоб" для n=100000 не быстро даже если считать по модулю.


Теорема Люка говорит нам, что для посчёта биномиального коэффициента достаточно будет сложить log₃N чисел.
В задаче ограничение на число элементов L = 100000.
Одиннадцать операций сложения — это не очень долго. Даже наоборот, достаточно быстро.
(в формуле в вики там умножение, но практичнее складывать логарифмы; а впрочем можно и умножать, не сильно медленнее)

const int inf = 65536;

// предпосчитанная таблица C^k_n, n=0..2, k=0..2

// BIN3LOG2[n][k] ≈ log_2(C^k_n mod 3)
const int BIN3LOG2[3][4] = {
    {0, -inf, -inf},
    {0,    0, -inf},
    {0,    1,    0},
};

// экспонента: 2^x mod 3
int pow2mod3(int x) {
    return (x < 0) ? 0 : 1 + (x & 1);
}

// вычисление C^k_n, где n, k записаны в троичной системе счисления
int b(const char nv[], const char kv[], const size_t l) {
    int rl = 0;
    for (size_t i = 0; i < l; ++i) {
        rl += BIN3LOG2[nv[i]][kv[i]];
    }
    return pow2mod3(rl);
}

	остальное
	char solve(const string& l) { size_t n = l.size(); const std::vector<char> bc = binomial(n - 1); int r = 0; for (size_t i = 0; i < n; ++i) { r += l[i] * bc[i]; } r <<= ~n & 1; return "BRGBRG"[r % 3 + 3]; } Лень делать совсем уж быстро, поэтому функция подсчёта строки треугольника Паскаля сделана отдельно и с выделением памяти, а не inplace. Зато сразу видно, что в решении нет ничего кроме скалярного произведения и учёта чётности.   binomial Тут только одна содержательная строка, остальное — перевод в троичную систему счисления и инкремент в ней же std::vector<char> binomial(size_t n) { std::vector<char> r; r.reserve(n + 1); std::vector<char> nv; // n в троичной системе счисления for (size_t tn = n; tn; tn /= 3) { nv.push_back(tn % 3); } nv.push_back(0); std::vector<char> kv(nv.size(), 0); // k в троичной системе счисления for (size_t k = 0; k <= n; ++k) { r.push_back(b(nv.data(), kv.data(), nv.size() - 1)); for (size_t t = 0; ; t++) { if (kv[t] == 2) { kv[t] = 0; } else { kv[t] += 1; break; } } } return r; }

Кстати, fun fact: можно исходный вектор символов не приводить к 0,1,2, так как ascii-коды символов RGB уже имеют различные остатки от деления на 3. Сразу можно символы на биномиальные коэффициенты умножать




Б>Наверное, для ускорения расчетов надо учитывать повторяющиеся паттерны
Да, можно.
Например, учитывать, что треугольник симметричный и поэтому можно вычислить лишь половину коэффициентов, и исходную строку можно предварительно сложить со своим реверсом и дальше обрабатывать тоже только первую половину.
Или не вычислять коэффициенты подряд, а поменять циклы местами — тогда можно будет отбрасывать весь интервал, если встретился нулевой множитель, так как финальные коэффициенты на нём также будут нулевые.
Ну или банально векторизовать вычисления — тут всё очень регулярно и с минимум ветвлений.
Впрочем, кажется, эти идеи ускорят вычисление максимум в несколько раз, и не окупятся тут по соотношению ускорение/трудозатраты