Розв'язок задачі SubmultiplesOfN з Топкодер.

У цьому пості розгляну як розв'язати задачу SubmultiplesOfN. Це задача середньої складності з першого дивізіону, що була частиною SRM 805. У ній потрібно було знайти скільки разів зустрічаються всі можливі кратні числу $N$ в числі $B$. Під зустрічаються мається на увазі чи є число представлене в текстовому вигляді в десятковій системі підпослідовністю такого ж представлення іншого числа. Наприклад, "23" зустрічається в "213", але не в "312".

Для розв'язання цієї задачі ми використаємо динамічне програмування.

Для того, щоб зрозуміти, що покласти в кожну комірку таблиці нам треба згадати, що в десятковій системі $abcd = ((a \times 10 + b) \times 10 + c) \times 10 + d. $ І ще, що для будь-якого додатного $N $ $abcd \% N = ((a \times 1000) \% N + (b \times 100) \% N + (c \times 10) \% N + d \% N) \% N. $

Зауважимо, що якщо $a \% N$ рівне нулю, то $a$ кратне $N$, тобто, якщо $a$ присутнє в $B,$ то ми вже маємо врахувати це додавши одиничку до відповіді. Власне, саме таку перевірку для всіх цифр окрім нуля ми і робимо коли ініціалізуємо перший рядок таблиці.

Виходить, що кожна комірка $(i, j)$ представляє всі можливі числа, що закінчуються на $B[i],$ зустрічаються в $B[0..i]$ і мають залишок $j$ при діленні на $N.$

const auto Mod = 1000000007ll;

const auto MaxDigitsCount = 5000;
const auto MaxN = 1000;
const auto Base = 10;

long long DP[MaxDigitsCount + 1][MaxN + 1];
long long Next[MaxDigitsCount + 1][Base];

class Solution {

    static const auto kNoPosistion = -1;

    // Швидкий пошук необхідної цифри починаючи із заданої позиції
    void InitTransitions(string b)
    {
        const auto len = (int)b.length();
        
        for (auto d = 0; d < Base; ++d)
        {
            Next[len][d] = kNoPosistion;
        }

        for (auto i = len - 1; i >= 0; --i)
        {
            for (auto d = 0; d < Base; ++d)
            {
                Next[i][d] = Next[i + 1][d];
            }
            Next[i][b[i] - '0'] = i;
        }
    }

public:
    int count(string B, int N)
    {
        InitTransitions(B);

        auto result = (long long)0;

        const auto len = (int)B.length();
        
        for (auto i = 0; i < len + 1; ++i)
        {
            for (auto j = 0; j < N + 1; ++j)
            {
                DP[i][j] = 0;
            }
        }

        // Ініціалізуємо перший рядок таблиці
        for (auto d = 1; d < Base; ++d)
        {
            const auto nextDigitPosition = Next[0][d];

            if (nextDigitPosition != kNoPosistion)
            {
                const auto reminder = d % N;
                DP[nextDigitPosition][reminder] += 1;

                if (reminder == 0)
                {
                    result += 1;
                }
            }
        }

        for (auto position = 0; position < len - 1; ++position)
        {
            for (auto reminder = 0; reminder < N; ++reminder)
            {
                for (auto d = 0; d < Base; ++d)
                {
                    const auto nextDigitPosition = Next[position + 1][d];
                    
                    if (nextDigitPosition != kNoPosistion)
                    {
                        const auto appended = reminder * 10 + d;
                        const auto newReminder = appended % N;
                        const auto upToD = DP[position][reminder];

                        (DP[nextDigitPosition][newReminder] += upToD) %= Mod;

                        if (newReminder == 0)
                        {
                            (result += upToD) %= Mod;
                        }
                    }
                }
            }
        }

        return result;
    }
};

#pragma comment(linker, "/STACK:200000000")

int main()
{
    // В дужках правильна відповідь.
    cout << Solution().count("12", 2) << " (2)" << endl;
    cout << Solution().count("14", 7) << " (1)" << endl;
    cout << Solution().count("10", 2) << " (1)" << endl;
    cout << Solution().count("12345678", 2) << " (170)" << endl;
    cout << Solution().count("1111111111", 7) << " (1)" << endl;
    cout << Solution().count("1357913579135791357913579", 2) << " (0)" << endl;
    cout << Solution().count("1122334455", 6) << " (20)" << endl;
    cout << Solution().count("1020402", 24) << " (6)" << endl;
    cout << Solution().count("123456789012345678901234567890", 1) << " (62224120)" << endl;
    
}