How can I count valid numbers for this old C++ competition problem?

Keep counts by checksum remainder. The checksum is linear modulo 19, so you only need 19 states rather than all possible digit strings.

First enumerate valid dates from year 1 through 9999. Format each as eight digits, discard dates that do not match the input, and increment dateCount[r], where r is the weighted sum of those eight digits modulo 19. That is fewer than four million dates, so it is manageable.

For the ten arbitrary digits, start with dp[0] = 1. Process each position using its weight. For every current remainder r and every digit d allowed by the input, add dp[r] to next[(r + weight * d) % 19]. Replace dp with next after each position.

Finally, combine dateCount[a] and dp[b]. For each pair, compute s = (a + b) % 19 and k = s <= 9 ? s : 19 - s. Add dateCount[a] * dp[b] if the last input character is X or equals k. Use long long for the counts and products.

The date and the ten arbitrary digits can be counted separately, but their totals cannot just be multiplied if K is fixed. Their weighted sums interact through the checksum.

There is a shortcut when K is X. Every valid choice of the first 18 digits determines exactly one check digit, so you can multiply the number of matching valid dates by 10 for each X among the ten arbitrary digits. No remainder DP is needed in that case.

For the date enumeration, use the Gregorian leap-year rule: divisible by 400, or divisible by 4 but not by 100. Check the actual day limit for each month, and compare all eight formatted date digits against the pattern, including leading zeroes.

It is also worth testing year 0000 as invalid, February 29 in years 1900 and 2000, and a pattern with a fixed K of 0. Those catch several easy boundary mistakes.