以下の補題の答えを \(f(B_{1}, B_{2}, B_{3})\) とおきます。

整数の組 \((Y_{1}, Y_{2})\) のうち、以下の条件を全て満たすものは何通りですか

• \(10^{B_{1}}\leq Y_{1}\)
• \(10^{B_{2}}\leq Y_{2}\)
• \(Y_{1} + Y_{2}<10^{B_{3}}\)

求めたいものは、以下の条件を全て満たす整数の組 \((X_{1}, X_{2})\) の場合の数です。

• \(10^{A_{1} - 1} \leq X_{1}\)
• \(10^{A_{2}-1} \leq X_{2}\)
• \(X_{1} + X_{2} \leq 10^{A_{3}}\)
• \(10^{A_{1}} \leq X_{1}\) を満たさない
• \(10^{A_{2}} \leq X_{2}\) を満たさない
• \(X_{1}+X_{2}\leq10^{A_{3}-1}\) を満たさない

包除原理を用いると、この問題の答えは \(f\) を用いて以下のように表すことができます。

\[\sum_{i=0}^{1}\sum_{j=0}^{1}\sum_{k=0}^{1}f(A_{1} - i, A_{2} - j, A_{3} - k)(-1)^{i+j+k} \]

よって、\(f(B_{1},B_{2},B_{3})\) を高速に求める関数を実装できれば良いです。 \(f(B_{1},B_{2},B_{3})\) については、以下が成り立ちます。

• \(B_{3}\leq \max(B_{1}, B_{2})\) ならば \(0\)
• \(B_{3}> \max(B_{1}, B_{2})\) ならば \(\dfrac{(10^{B_{3}}-10^{B_{1}}-10^{B_{2}})(10^{B_{3}}-10^{B_{1}}-10^{B_{2}} + 1)}{2}\)

以上より\(f(B_{1},B_{2},B_{3})\) は時間計算量 \(O(\log(B_{3}))\) で求めることができるため、この問題は \(1\) つのテストケースにつき、時間計算量 \(O(\log(A_{3}))\) で解くことができます。

c++ による実装例

python による実装例

MOD = 998244353

def f(b1, b2, b3):
    if max(b1, b2) >= b3:
        return 0
    tmp = pow(10, b3, MOD) - pow(10, b1, MOD) - pow(10, b2, MOD)
    return (tmp + 1) * tmp // 2

T = int(input())
for _ in range(T):
    a1, a2, a3 = map(int,input().split())
    ans = 0
    pm = 1
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ans = (ans + f(a1 - i, a2 - j, a3 - k) * pm) % MOD
                pm *= -1
            pm *= -1
        pm *= -1
    print(ans)