gistfile1.cpp

#include <iostream>
#include <vector>

int main(int argc, char** argv) {
    // All valid digits given previous two digits.
    std::vector<int> valid_digits[100];

    for (int i = 0; i < 100; ++i) {
        int d0 = i % 10;
        int d1 = i / 10;
        
        for (int d2 = 0; d2 < 10; ++d2) {
            if (d0 + d1 + d2 > 9) continue;
            valid_digits[i].push_back(d2);
        }
    }

    // Number of valid n-digit numbers given two leading digits.
    uint64_t num_valid[21][100] = { 0 };

    for (int i = 0; i < 10; ++i)  num_valid[1][i] = i;
    for (int i = 0; i < 100; ++i) num_valid[2][i] = (i / 10 + i % 10 <= 9);

    for (int i = 3; i <= 20; ++i) {
        for (int digits = 0; digits < 100; ++digits) {
            uint64_t count = num_valid[i-1][digits];

            for (auto digit : valid_digits[digits]) {
                int new_digits = digit * 10 + digits/10;
                num_valid[i][new_digits] += count;
            }
        }
    }

    uint64_t sum = 0;
    for (int i = 10; i < 100; ++i) sum += num_valid[20][i];
    std::cout << sum << "\n";
    
    return 0;
}