The Brilliant Calculator

Computer Science Level 4

Suppose that you have a calculator with number 0~9, plus and minus button. You play around with this calculator and try to enumerate all the possibilities.

Since this calculator has exactly $n$ segments to display the numbers and operators, this calculator only support expressions with length of exactly $n$ . A valid expression of the calculator is a string consists of 0~9, +, - , with length $n$ , and it follows the mathematical format: operators cannot appear in the first or last position, and operators can't be next to each other. For instance, for $n=5$ , +1234, -1234, 1+23+, 12++3, 1234+5 are not valid expressions, while 123+4, 12-34, 012+3, 00+00 are valid expressions.

Note that leading zeros are allowed in the calculator, and leading zeros are automatically ignored during the calculation (but they do contribute to the length of the expression). For instance, 00012+0034 will be treated as 12+34 in regular format, but it has length 10.

As long as you input a valid expression, the calculator will immediately output the result. If you input 00012+0034, then it will output 46.

You don't have too much time and patience to enumerate all the valid expressions, but you are very interested in this problem: Given that $n=2021$ , what is the sum of the results of all the valid expressions of this calculator?

Let $S$ be the answer of the problem. Since the answer may be too large, you just need to submit $S\bmod{ 998244353}.$

The answer is 699001210.

1 solution

Nick Kent
May 8, 2021

The following is the Python code used:

S = dict()
n = 2021

for k in range(1, n+1):
    s = ((10**n) * (10**n-1)) // 2
    for i in range(1, k-1):
         s += S[i] * 2 * (10 ** (k - i - 1))
    S[k] = s

print(S[n] % 998244353)

The Brilliant Calculator

The answer is 699001210.

1 solution

0 pending reports