#869214 (D) No.2302 Carry X Times

• 問題: No.2302 Carry X Times
• ユーザー: Daylight
• 提出日時: 2023-05-13 15:32:14
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 87 ms / 2,000 ms
• コード長: 14,868 bytes
• コンパイル時間: 3,192 ms
• コンパイル使用メモリ: 238,196 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-22 17:57:13
• 合計ジャッジ時間: 5,621 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	40 ms; 6,816 KB
testcase_01	AC	29 ms; 6,816 KB
testcase_02	AC	32 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	1 ms; 6,940 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	86 ms; 6,948 KB
testcase_11	AC	84 ms; 6,940 KB
testcase_12	AC	85 ms; 6,944 KB
testcase_13	AC	83 ms; 6,944 KB
testcase_14	AC	82 ms; 6,944 KB
testcase_15	AC	84 ms; 6,944 KB
testcase_16	AC	85 ms; 6,940 KB
testcase_17	AC	87 ms; 6,940 KB
testcase_18	AC	85 ms; 6,940 KB
testcase_19	AC	82 ms; 6,944 KB
testcase_20	AC	83 ms; 6,940 KB
testcase_21	AC	86 ms; 6,940 KB
testcase_22	AC	83 ms; 6,944 KB
testcase_23	AC	86 ms; 6,940 KB
testcase_24	AC	87 ms; 6,940 KB

ソースコード

public import std;

DList!string scan_buffer;
DList!char char_buffer;
static this() {
    scan_buffer = DList!(string)();
    char_buffer = DList!(char)();
}

void cin()() {

}

void cin(T, A...)(ref T a, ref A tail) {
    import std.traits : isArray;

    static if (typeof(a).stringof == "string") {
        if (!char_buffer.empty) {
            a = char_buffer.array.map!(x => x.to!string).join();
            char_buffer.clear();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token;
        }
    } else static if (typeof(a).stringof == "char") {
        if (!char_buffer.empty) {
            a = char_buffer.front();
            char_buffer.removeFront();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token[0];
            if (token.length > 1) {
                foreach (c; token[1 .. $]) {
                    char_buffer.insertBack(c);
                }
            }
        }
    } else static if (typeof(a).stringof == "char[]") {
        if (a.length == 0) {
            string token;
            cin(token);
            foreach (c; token) {
                a ~= c;
            }
        } else {
            foreach (ref v; a) {
                cin(v);
            }
        }
    } else static if (isArray!(typeof(a))) {
        foreach (ref v; a) {
            cin(v);
        }
    } else static if (isTuple!(typeof(a))) {
        foreach (i, _; a) {
            cin(a[i]);
        }
    } else {
        if (!char_buffer.empty) {
            writeln(char_buffer.array.map!(x => x.to!string));
            a = char_buffer.array.map!(x => x.to!string).join().to!T;
            char_buffer.clear();
        } else {
            while (scan_buffer.empty) {
                foreach (t; readln.split) {
                    if (t.length == 0) {
                        continue;
                    }
                    scan_buffer.insert(t);
                }
            }
            auto token = scan_buffer.front;
            scan_buffer.removeFront();
            a = token.to!T;
        }
    }
    cin(tail);
}

bool chmin(T)(ref T a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

bool chmax(T)(ref T a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

alias PQueue(T = long, alias less = "a<b") = BinaryHeap!(Array!T, less);


import std.typecons : Tuple;

ulong safeMod(long x, long m) @safe pure nothrow @nogc
{
    x %= m;
    if (x < 0)
        x += m;
    return x;
}

ulong[2] umul128(ulong a, ulong b) @safe @nogc pure nothrow
{
    immutable ulong au = a >> 32;
    immutable ulong bu = b >> 32;
    immutable ulong al = a & ((1UL << 32) - 1);
    immutable ulong bl = b & ((1UL << 32) - 1);

    ulong t = al * bl;
    immutable ulong w3 = t & ((1UL << 32) - 1);
    ulong k = t >> 32;
    t = au * bl + k;

    k = t & ((1UL << 32) - 1);
    immutable ulong w1 = t >> 32;
    t = al * bu + k;
    k = t >> 32;
    return [au * bu + w1 + k, t << 32 + w3];
}

struct Barrett
{
    uint _m;
    ulong im;
    this(uint m) @safe @nogc pure nothrow
    {
        _m = m;
        im = (cast(ulong)(-1)) / m + 1;
    }

    uint umod() @safe @nogc pure nothrow
    {
        return _m;
    }

    uint mul(uint a, uint b) @safe @nogc pure nothrow
    {
        ulong z = a;
        z *= b;
        immutable ulong x = umul128(z, im)[0];
        uint v = cast(uint)(z - x * _m);
        if (_m <= v)
            v += _m;
        return v;
    }
}

long ctPowMod(long x, long n, int m) @safe pure nothrow @nogc
{
    if (m == 1)
        return 0;
    uint _m = cast(uint) m;
    ulong r = 1;
    ulong y = safeMod(x, m);
    while (n)
    {
        if (n & 1)
            r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

bool ctIsPrime(int n) @safe pure nothrow @nogc
{
    if (n <= 1)
        return false;
    if (n == 2 || n == 7 || n == 61)
        return true;
    if (n % 2 == 0)
        return false;
    long d = n - 1;
    while (d % 2 == 0)
        d /= 2;
    foreach (a; [2, 7, 61])
    {
        long t = d;
        long y = ctPowMod(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1)
        {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0)
        {
            return false;
        }
    }
    return true;
}

enum bool isPrime(int n) = ctIsPrime(n);

Tuple!(long, long) invGcd(long a, long b) @safe pure nothrow @nogc
{
    a = safeMod(a, b);
    if (a == 0)
        return Tuple!(long, long)(b, 0);
    long s = b, t = a, m0 = 0, m1 = 1;
    while (t)
    {
        immutable long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        long tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0)
        m0 += b / s;
    return Tuple!(long, long)(s, m0);
}

int ctPrimitiveRoot(int m) @safe pure nothrow @nogc
{
    if (m == 2)
        return 1;
    if (m == 167_772_161)
        return 3;
    if (m == 469_762_049)
        return 3;
    if (m == 754_974_721)
        return 11;
    if (m == 998_244_353)
        return 3;
    int[20] divs;
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0)
        x /= 2;
    for (int i = 3; (cast(long) i) * i <= x; i += 2)
        if (x % i == 0)
        {
            divs[cnt++] = i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        divs[cnt++] = x;
    for (int g = 2;; g++)
    {
        bool ok = true;
        foreach (i; 0 .. cnt)
            if (ctPowMod(g, (m - 1) / divs[i], m) == 1)
            {
                ok = false;
                break;
            }
        if (ok)
            return g;
    }
}

enum primitiveRoot(int m) = ctPrimitiveRoot(m);

struct StaticModInt(int m) if (1 <= m) {
    import std.traits : isSigned, isUnsigned, isSomeChar;

    alias mint = StaticModInt;
public:
    static int mod() {
        return m;
    }

    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    this(T)(T v) if (isSigned!T) {
        long x = cast(long)(v % cast(long)(umod()));
        if (x < 0)
            x += umod();
        _v = cast(uint)(x);
    }

    this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
        _v = cast(uint)(v % umod());
    }

    this(bool v) {
        _v = cast(uint)(v) % umod();
    }

    auto opAssign(T)(T v)
            if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
        return this = mint(v);
    }

    inout uint val() pure {
        return _v;
    }

    ref mint opUnary(string op)() pure nothrow @safe if (op == "++") {
        _v++;
        if (_v == umod())
            _v = 0;
        return this;
    }

    ref mint opUnary(string op)() pure nothrow @safe if (op == "--") {
        if (_v == 0)
            _v = umod();
        _v--;
        return this;
    }

    mint opUnary(string op)() if (op == "+" || op == "-") {
        mint x;
        return mixin("x " ~ op ~ " this");
    }

    ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
        mint y = value;
        return opOpAssign!(op)(y);
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
        _v += value._v;
        if (_v >= umod())
            _v -= umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
        _v -= value._v;
        if (_v >= umod())
            _v += umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
        ulong z = _v;
        z *= value._v;
        _v = cast(uint)(z % umod());
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
        return this = this * value.inv();
    }

    ref mint opOpAssign(string op, T)(T value)
            if (op == "^^" && (is(T == int) || is(T == long))) {
        return this = this.pow(value);
    }

    mint pow(long n) const pure {
        assert(0 <= n);
        mint x = this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    mint inv() const pure {
        static if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = invGcd(_v, mod());
            assert(eg[0] == 1);
            return mint(eg[1]);
        }
    }

    mint opBinary(string op, R)(const R value) const pure
    if (op == "+" || op == "-" || op == "*" || op == "/") {
        static if (is(R == mint)) {
            mint x;
            x += this;
            return x.opOpAssign!(op)(value);
        } else {
            mint x;
            x += this;
            mint y = value;
            return x.opOpAssign!(op)(y);
        }
    }

    mint opBinary(string op, R)(const R value) const pure
    if (op == "^^") {
        return pow(value);
    }

    mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
        mint y = value;
        return y.opBinary!(op)(this);
    }

    bool opEquals(R)(const R value) const {
        static if (is(R == mint)) {
            return _v == value._v;
        } else {
            mint y = mint(value);
            return this == y;
        }
    }

private:
    uint _v;
    uint umod() pure const {
        return m;
    }

    enum bool prime = isPrime!(m);
}

struct DynamicModInt(int id) {
    import std.traits : isSigned, isUnsigned, isSomeChar;

    alias mint = DynamicModInt;
public:
    static int mod() {
        return bt.umod();
    }

    static void setMod(int m) {
        assert(1 <= m);
        bt = Barrett(m);
    }

    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    this(T)(T v) if (isSigned!T) {
        long x = cast(long)(v % cast(long)(umod()));
        if (x < 0)
            x += umod();
        _v = cast(uint)(x);
    }

    this(T)(T v) if (isUnsigned!T || isSomeChar!T) {
        _v = cast(uint)(v % umod());
    }

    this(bool v) {
        _v = cast(uint)(v) % umod();
    }

    auto opAssign(T)(T v)
            if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) {
        return this = mint(v);
    }

    inout uint val() {
        return _v;
    }

    ref mint opUnary(string op)() nothrow @safe if (op == "++") {
        _v++;
        if (_v == umod())
            _v = 0;
        return this;
    }

    ref mint opUnary(string op)() nothrow @safe if (op == "--") {
        if (_v == 0)
            _v = umod();
        _v--;
        return this;
    }

    mint opUnary(string op)() if (op == "+" || op == "-") {
        mint x;
        return mixin("x " ~ op ~ " this");
    }

    ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) {
        mint y = value;
        return opOpAssign!(op)(y);
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) {
        _v += value._v;
        if (_v >= umod())
            _v -= umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) {
        _v -= value._v;
        if (_v >= umod())
            _v += umod();
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) {
        _v = bt.mul(_v, value._v);
        return this;
    }

    ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) {
        return this = this * value.inv();
    }

    ref mint opOpAssign(string op, T)(T value)
            if (op == "^^" && (is(T == int) || is(T == long))) {
        return this = this.pow(value);
    }

    mint pow(long n) const {
        assert(0 <= n);
        mint x = this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    mint inv() const {
        auto eg = invGcd(_v, mod());
        assert(eg[0] == 1);
        return mint(eg[1]);
    }

    mint opBinary(string op, R)(const R value)
            if (op == "+" || op == "-" || op == "*" || op == "/") {
        static if (is(R == mint)) {
            mint x;
            x += this;
            return x.opOpAssign!(op)(value);
        } else {
            mint y = value;
            return opOpAssign!(op)(y);
        }
    }

    mint opBinary(string op, R)(const R value) const
    if (op == "^^") {
        return pow(value);
    }

    mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) {
        mint y = value;
        return y.opBinary!(op)(this);
    }

    bool opEquals(R)(const R value) const {
        static if (is(R == mint)) {
            return _v == value._v;
        } else {
            mint y = mint(value);
            return this == y;
        }
    }

private:
    uint _v;
    static Barrett bt = Barrett(998_244_353);
    uint umod() {
        return bt.umod();
    }
}

alias modint998244353 = StaticModInt!(998244353);
alias modint1000000007 = StaticModInt!(1000000007);
alias modint = DynamicModInt!(-1);

alias mint = modint998244353;
void solve() {
    long N, X;
    cin(N, X);
    alias T = Tuple!(long, long, int, int);
    mint[T] memo;
    mint dfs(long Na, long Nb, int x, int c) {
        if (tuple(Na, Nb, x, c) in memo) {
            return memo[tuple(Na, Nb, x, c)];
        }
        if (Na == 0 && Nb == 0) {
            if (x == X)
                return memo[tuple(Na, Nb, x, c)] = mint(1);
            else
                return memo[tuple(Na, Nb, x, c)] = mint(0);
        }

        mint ret = 0;
        foreach (a; 0 .. 10) {
            if (Na < a)
                break;
            foreach (b; 0 .. 10) {
                if (Nb < b)
                    break;
                if (a + b + c >= 10) {
                    ret += dfs((Na - a) / 10, (Nb - b) / 10, x + 1, 1);
                } else {
                    ret += dfs((Na - a) / 10, (Nb - b) / 10, x, 0);
                }
            }
        }
        return memo[tuple(Na, Nb, x, c)] = ret;
    }

    dfs(N, N, 0, 0).val.writeln;
}

void main() {
    int T;
    cin(T);
    while (T--) {
        solve();
    }
}