AtCoder Regular Contest 178 B - 1 + 6 = 7

解法

以下 0-indexed であるとする。

まず $A_0 \lt A_1$ であるとして、 $A_2 = A_1$ または $A_2 = A_1 + 1$ の場合のみ考えれば良い。（そうでない場合は答えは $0$ である。）

$A_0$ 桁の正の整数と $A_1$ 桁の正の整数の和は $A_1$ 桁か $A_1 + 1$ 桁になるため、以下では $A_1$ 桁のものを数える。

もし $A_2 = A_1 + 1$ の場合、 $A_i$ 桁の正の整数は $9 \times 10^{A_i - 1}$ 個あるため、上で求めた場合の数を $9 \times 10^{A_0 - 1} \times 9 \times 10^{A_1 - 1}$ から引けば良い。

$X_0$ を固定したときに、 $X_1$ の桁数が変化しないような正の整数の個数を考える。自分は以下のように書きながら考えた。

A = {1, 1, 1}
X[0]  X[1]    
1    9 - 1
2    9 - 2
3    9 - 3
..............
8    9 - 8

A = {2, 2, 2}
X[0]    X[1]    
10    90 - 10
11    90 - 11
12    90 - 12
13    90 - 13
..............
89    90 - 89

A = {2, 3, 3}
X[0]     X[1]    
10    900 - 10
11    900 - 11
12    900 - 12
13    900 - 13
..............
89    900 - 89
90    900 - 90
..............
99    900 - 99

こんな感じで考えていくと、 $A_0 = A_1$ の場合だけ $X_0$ が大きいと対応する $X_1$ が存在しなくなってしまうことがわかるため、場合分けをする。

$9 \times 10^{n}$ 部分と $- X_0$ の部分で分けて計算すると、以下のようになる。

$A_0 = A_1$ のとき

$9 \times 10^{A_1 - 1} \times 8 \times 10^{A_0 - 1} - \frac{(9 \times 10^{A_0 - 1} )(9 \times 10^{A_0 - 1} - 1)}{2} +\frac{(10^{A_0 - 1} )( 10^{A_0 - 1} - 1)}{2}$

$A_0 \lt A_1$ のとき

$9 \times 10^{A_1 - 1} \times 9 \times 10^{A_0 - 1} - \frac{( 10^{A_0} )( 10^{A_0} - 1)}{2} +\frac{(10^{A_0 - 1} )( 10^{A_0 - 1} - 1)}{2}$

あとはこれを実装すれば良い。

#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint998;
using namespace std;

void solve() {
    VEC(i64, A, 3);
    if (A[0] > A[1]) swap(A[0], A[1]);
    // A[0] <= A[1]
    if (!(A[1] == A[2] or A[2] == A[1] + 1)) {
        print(0);
        return;
    }
    mint c0 = mint(9) * (mint(10).pow(A[0] - 1));
    mint c1 = mint(9) * (mint(10).pow(A[1] - 1));
    {
        // A[2] = A[1] となるものを数え上げる
        mint ans = 0;
        auto f = [](mint n) -> mint { return n * (n + 1) / 2; };
        if (A[0] == A[1]) {
            // A[0] == A[1]
            ans += c1 * (mint(8) * mint(10).pow(A[0] - 1));
            ans -= f(mint(9) * mint(10).pow(A[0] - 1) - 1);
            ans += f(mint(10).pow(A[0] - 1) - 1);
        } else {
            assert(A[0] < A[1]);
            ans += c0 * c1;
            ans -= f(mint(10).pow(A[0]) - 1);
            ans += f(mint(10).pow(A[0] - 1) - 1);
        }
        if (A[2] == A[1] + 1) {
            ans = c0 * c1 - ans;
        }
        print(ans);
    }
    /*
    {
        // 実験コード
        vector<i64> lb(3), ub(3);
        REP(i, 3) {
            lb[i] = TEN(A[i] - 1);
            ub[i] = TEN(A[i]) - 1;
        }
        int ans = 0;
        REP(x0, lb[0], ub[0] + 1) {
            REP(x1, lb[1], ub[1] + 1) {
                i64 x2 = x1 + x0;
                if (LEN(to_string(x2)) == A[2]) {
                    // show(make_tuple(x0, x1, x2));
                    ans++;
                }
            }
        }
        print(ans);
    }
    */
    return;
}

int main() {
    INT(T);
    REP(T) solve();
    return 0;
}