結果

問題 No.2291 Union Find Estimate
ユーザー DaylightDaylight
提出日時 2023-05-06 00:50:09
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 17,129 bytes
コンパイル時間 4,556 ms
コンパイル使用メモリ 229,248 KB
実行使用メモリ 13,060 KB
最終ジャッジ日時 2023-09-04 20:15:04
合計ジャッジ時間 7,364 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 202 ms
4,408 KB
testcase_03 AC 30 ms
13,060 KB
testcase_04 AC 23 ms
4,448 KB
testcase_05 AC 23 ms
4,424 KB
testcase_06 AC 15 ms
4,384 KB
testcase_07 AC 9 ms
4,568 KB
testcase_08 AC 20 ms
4,392 KB
testcase_09 AC 20 ms
4,408 KB
testcase_10 AC 29 ms
4,404 KB
testcase_11 AC 39 ms
4,408 KB
testcase_12 AC 58 ms
4,392 KB
testcase_13 AC 23 ms
12,688 KB
testcase_14 AC 25 ms
4,412 KB
testcase_15 AC 30 ms
12,288 KB
testcase_16 AC 25 ms
4,672 KB
testcase_17 AC 20 ms
4,672 KB
testcase_18 AC 20 ms
4,644 KB
testcase_19 AC 29 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);


class Dsu {
public:
    this(long n) @safe nothrow {
        _n = cast(int) n, parent_or_size = new int[](n);
        parent_or_size[] = -1;
    }

    int merge(long a, long b) @safe nothrow @nogc {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y)
            return x;
        if (-parent_or_size[x] < -parent_or_size[y]) {
            auto tmp = x;
            x = y;
            y = tmp;
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(long a, long b) @safe nothrow @nogc {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }


    int leader(long a) @safe nothrow @nogc {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0)
            return cast(int) a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(long a) @safe nothrow @nogc {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    int[][] groups() @safe nothrow {
        auto leader_buf = new int[](_n), group_size = new int[](_n);
        foreach (i; 0 .. _n) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        auto result = new int[][](_n);
        foreach (i; 0 .. _n)
            result[i].reserve(group_size[i]);
        foreach (i; 0 .. _n)
            result[leader_buf[i]] ~= i;
        int[][] filtered;
        foreach (r; result)
            if (r.length != 0)
                filtered ~= r;
        return filtered;
    }

private:
    int _n;
    int[] parent_or_size;
}


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 main() {
    int W, H;
    cin(W, H);
    auto key = new int[W];
    key.fill(-1);
    auto dsu = new Dsu(W);
    bool zero = false;
    int und = W;
    foreach (i; 0 .. H) {
        auto Q = new char[W];
        cin(Q);
        auto ch = new int[26];
        ch.fill(-1);
        foreach (j, c; Q) {
            if (c == '?')
                continue;
            if (c >= '0' && c <= '9') {
                int u = dsu.leader(j);
                if (key[u] == -1) {
                    key[u] = c - '0';
                    und--;
                } else if (key[u] != c - '0') {
                    zero = true;
                }
            } else {
                if (ch[c - 'a'] == -1) {
                    ch[c - 'a'] = cast(int) j;
                } else {
                    int u = dsu.leader(ch[c - 'a']);
                    int v = dsu.leader(j);
                    if (dsu.same(u, v)) {
                        continue;
                    }
                    if (key[u] != -1 && key[v] != -1 && key[u] != key[v]) {
                        zero = true;
                    } else {
                        int k = -1;
                        k.chmax(key[u]);
                        k.chmax(key[v]);
                        if (key[u] != key[v] || key[u] == -1) {
                            und--;
                        }
                        int r = dsu.merge(u, v);
                        key[r] = k;
                    }
                }
            }
        }
        if (zero) {
            0.writeln;
        } else {
            (mint(10) ^^ und).val.writeln;
        }
    }
}
0