Leetcode. 2221. Треугольная сумма массива. Казалось бы, при чём здесь Паскаль?

В общем-то, задача не особо сложная, в комментариях куча выпускников видеокурсов, закодивших решение "в лоб" на своём любимом Питончике, удивляются, почему у неё уровень Medium, а не Easy. Сложность, как обычно, заключается в том, чтобы сделать качественно: чтобы тесты проходили за единицы миллисекунд, а не за 700 (C++) или 1200 (Питончик).

Есть массив десятичных цифр 'a'. Суммируем попарно все цифры: a[0] + a[1], a[1] + a[2] и т.д., и берём каждую сумму по модулю 10. Получается новый массив десятичных цифр на единицу меньшей размерности. Повторяем процедуру, пока не остаётся одна цифра. Она - и есть ответ.
Здесь - подробности, картинки, граничные условия и тест кейсы: https://leetcode.com/problems/find-triangular-sum-of-an-array/

Кто сказал "рекурсия"? А, это нейросеть. Ладно, что с неё возьмёшь, она же думать не умеет...
В общем-то, если посмотреть, сколько раз каждая исходная цифра входит в итоговую сумму, то можно заметить закономерность:

 длина массива   веса элементов в итоговой сумме

    1                     1

    2                   1   1

    3                 1   2   1

    4               1   3   3   1

    5             1   4   6   4   1

           ... 

Нам нужна строка № n-1 треугольника Паскаля, где n - длина исходного массива, и тогда ответом будет скалярное произведение по модулю 10 этой строки и массива, рассматриваемых как векторы. Проблемка только одна: n принимает значения до 500, а как известно, точное представление максимального биномиального коэффициента в этом ряду C(500; 250) требует очень много бит. Много бит - много вычислений, и вот мы уже почти в топе, но с другой стороны (где времена максимальные). Вычислять же биномиальные коэффициенты классической формулой

  C(n; k) = C(n; k - 1) * (n - k + 1) / k 

но по модулю 10 мы не можем, т. к. делимое в этой операции требуется полностью. Но зато нам и весь коэффициент не нужен, а хватит его последней циферки.

Естественно, существуют и другие варианты:

• Тупо просуммировать числа 500*499/2 ~ 125000 раз и столько же раз взять остатки от деления. Это неспортивно, и такими решениями заполнен диапазон от 170 до 700 мс в разделе C++ (в других не смотрел, но говорят, Чарльз Бэббидж на своём арифмометре считает быстрее тех решений).
• Можно брать остаток не каждый раз, а где-то по достижении суммой значения 2⁶³, сэкономив на тяжёлых делениях. Но плохая асимптотика никуда не денется. Да и ещё неизвестно, что хуже, деление или if для его обхода.
• Один лихой решатель просуммировал динамическим программированием не сами числа, а треугольник Паскаля по модулю 10, и потом сосчитал скалярное произведение. Так себе затея, как по мне, но 20 мс выжать у него получилось.

В общем, эти способы не подходят, если мы хотим достичь заветных 7 мс (быстрее пока реализовать не смогли даже по Лукасу с табличками заранее посчитанных остатков и малых комбинаций). Нужно нормальное решение.

 class Solution { 

public: 

    int triangularSum(vector& nums) noexcept { 

        ios::sync_with_stdio(false); 

        cin.tie(); 

        constexpr auto ten = 10; 

        const auto first = &nums[0]; 

        const auto end = &nums[1]; 

        auto last = &nums[nums.size()]; 

        auto count = 0; 

        while (last != end) { 

            for (auto prev = first, next = end; next != last; ++prev, ++next) {

                *prev += *next; 

            } 

            if (!(++count % 27)) { 

                for (auto begin = first; begin != last; ++begin) { 

                    *begin %= ten; 

                } 

            } 

            --last; 

        } 

        return nums[0] % ten; 

    } 

}; 

 def pascal_row_mod10(n): 

    row = [1] 

    for k in range(n): 

        row.append((row[-1] * (n - k)) // (k + 1) % 10) 

    return row[:n//2+1] + row[:n//2][::-1] 

 def dot_mod10(a, b): 

    return sum(x*y for x, y in zip(a, b)) % 10 

 def triangular_sum(array): 

    n = len(array) 

    pascal_row = pascal_row_mod10(n) 

    return dot_mod10(array, pascal_row)