Я предполагаю, что формула в указанной вами ссылке верна:
Чтобы избежать целочисленного переполнения, мы будемнеобходимо применять эти по модулю арифметических правил :
(a * b) mod c = ((a mod c) * (b mod c)) mod c
(a ± b) mod c = ((a mod c) ± (b mod c)) mod c
Применяя их к формуле:
Но как рассчитать
... без непосредственного расчета самого коэффициента (который может вызвать переполнение)?
Поскольку 3 - простое число, это можно сделать с помощью Теорема Лукаса :
... где n_i, m_i - это i -ые цифры n, m в base-3 .
Преобразование в base-3 легко с целочисленным делением:
// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
unsigned i = 0;
while (i < max && n > 0)
{
out[i] = n % 3;
n /= 3;
i++;
}
return i;
}
Обратите внимание, что, поскольку n_i, m_i всегда находятся в диапазоне [0, 2] (потому что они являются base-3)цифры), C(n_i, m_i) очень легко вычислить:
// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
if (n < k)
return 0;
switch (n)
{
case 0:
case 1:
return 1;
case 2:
return 1 + (k == 1);
// shouldn't happen
default:
return 0;
}
}
А теперь сама теорема:
// Lucas's theorem for p = 3
unsigned lucas_3(
unsigned len_n, const unsigned * dig_n,
unsigned len_k, const unsigned * dig_k
)
{
// use modulo product rule:
// prod[i] % 3 = ((prod[i - 1] % 3) * value[i])
unsigned prod = 1;
for (unsigned i = 0; i < len_n; i++) {
unsigned n_i = dig_n[i];
unsigned k_i = (i < len_k) ? dig_k[i] : 0;
prod = (prod * binom_max_2(n_i, k_i)) % 3;
}
return prod % 3;
}
Преобразование символов:
// convert from 012 to RGB
char int_2_char(int i)
{
switch (i) {
case 0: return 'R';
case 1: return 'G';
case 2: return 'B';
// shouldn't happen
default:
return '\0';
}
}
// convert from RGB to 012
unsigned char_2_int(char c)
{
switch (c) {
case 'R': return 0;
case 'G': return 1;
case 'B': return 2;
// shouldn't happen
default:
return 3;
}
}
Наконец,алгоритм треугольника:
// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11
// main algorithm function
char triangle(const char * input)
{
unsigned sum = 0;
const int n = strlen(input);
// calculate digits of n - 1
unsigned dig_n[MAX_N_LOG_3];
unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);
for (unsigned km1 = 0; km1 < n; km1++)
{
// calculate digits of k - 1
unsigned dig_k[MAX_N_LOG_3];
unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);
// calculate C(n - 1, k - 1) mod 3
unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);
// add using the modulo rule
sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
}
// value of (-1) ** (n - 1)
// (no need for pow; just need to know if n is odd or even)
int sign = (n % 2) * 2 - 1;
// for negative numbers, must resolve the difference
// between C's % operator and mathematical mod
int sum_mod3 = (3 + (sign * (int)(sum % 3)) % 3;
return int_2_char(sum_mod3);
}
Приведенный выше код проходит все тесты;обратите внимание, что он был написан в пользу ясности, а не производительности.
Так почему же этот код смог пройти все тесты в назначенное время, тогда как простой табличный подход не был?Из-за сложности времени :
Подход на основе таблиц обрабатывает все уровни треугольника, который равен O(n^2) (см. Треугольные числа ).
Конечно, используя алгоритм Лукаса, нужно обрабатывать только верхний уровень;однако сам алгоритм равен O(log n), поскольку он проходит через каждую цифру n (независимо от базы).Общая сложность составляет O(n log n), что все еще представляет собой значительное улучшение.