#1169179 (D) No.2215 Slide Subset Sum

• 問題: No.2215 Slide Subset Sum
• ユーザー: InTheBloom
• 提出日時: 2026-06-16 18:45:18
• 言語: D (dmd 2.112.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,569 bytes
• コンパイル時間: 4,302 ms
• コンパイル使用メモリ: 196,480 KB
• 実行使用メモリ: 432,172 KB
• 最終ジャッジ日時: 2026-06-16 18:46:00
• 合計ジャッジ時間: 10,654 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	-- * 2
other	TLE * 1 -- * 44

ソースコード

import std;

void main () {
    const long MOD = 998244353;
    int N, M, K;
    readln.read(N, M, K);
    auto A = readln.split.to!(int[]);

    alias T = long[100];
    T op (T a, T b) {
        T ret;
        foreach (i; 0 .. K) {
            foreach (j; 0 .. K) {
                ret[(i + j) % K] += a[i] * b[j] % MOD;
                ret[(i + j) % K] %= MOD;
            }
        }
        return ret;
    }
    T e () {
        T ret;
        ret[0]++;
        return ret;
    }

    auto seg = new SegmentTree!(T, op, e)(N);
    foreach (i; 0 .. N) {
        T v;
        v[A[i]]++;
        v[0]++;
        seg.set(i, v);
    }

    auto ans = new long[](N - M + 1);
    foreach (i; 0 .. N - M + 1) {
        ans[i] = seg.prod(i, i + M)[0] - 1;
    }

    writefln("%(%s\n%)", ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

class SegmentTree (T, alias op, alias e) {
    import std.format;
    import std.traits;

    static assert(is(Unqual!(T) == T),
            "[ERROR] SegmentTree: T must be an unqualified type.");
    static assert(__traits(compiles, op(T.init, T.init)),
            format("[ERROR] SegmentTree: op(%s, %s) must be callable.", T.stringof, T.stringof));
    static assert(is(typeof(op(T.init, T.init)) == T),
            format("[ERROR] SegmentTree: op(%s, %s) must return %s, but it returns %s.",
                T.stringof, T.stringof, T.stringof, typeof(op(T.init, T.init)).stringof));
    static assert(__traits(compiles, e()),
            "[ERROR] SegmentTree: e() must be callable.");
    static assert(is(typeof(e()) == T),
            format("[ERROR] SegmentTree: e() must return %s, but it returns %s.", T.stringof, typeof(e()).stringof));


    size_t length;
    int leafs;
    T[] node;

    this (size_t N) {
        struct ERange {
            size_t rem;
            size_t length () {
                return rem;
            }
            bool empty () {
                return rem == 0;
            }
            T front () {
                return e();
            }
            void popFront () {
                rem--;
            }
        }

        this(ERange(N));
    }

    this (R) (R range)
    if (isInputRange!(R) && isImplicitlyConvertible!(ForeachType!(R), T) && hasLength!(R))
    {
        length = range.length;
        enforce(1 <= length,
                "[ERROR] SegmentTree: length must be positive.");

        leafs = 1;
        while (leafs < length) {
            leafs *= 2;
        }

        // 全体で2 * leafs - 1ノード必要
        // 1-indexedで使う
        node.length = 2 * leafs;

        foreach (i; 0 .. leafs) {
            T v = e();
            if (!range.empty()) {
                v = range.front();
                range.popFront();
            }
            node[i + leafs] = v;
        }

        foreach_reverse (i; 1 .. leafs) {
            node[i] = op(node[2 * i], node[2 * i + 1]);
        }
    }

    void set (size_t i, T v) {
        enforce(i < length,
                format("[ERROR] SegmentTree.set: index %s is out of range [0, %s).",
                    i, length));

        size_t cur = i + leafs;
        node[cur] = v;
        cur /= 2;
        while (1 <= cur) {
            node[cur] = op(node[2 * cur], node[2 * cur + 1]);
            cur /= 2;
        }
    }

    T get (size_t i) {
        enforce(i < length,
                format("[ERROR] SegmentTree.get: index %s is out of range [0, %s).",
                i, length));
        return node[i + leafs];
    }

    T prod (size_t l, size_t r) {
        enforce(l <= r,
            format("[ERROR] SegmentTree.prod: invalid range [%s, %s): l must be <= r.",
                   l, r));
        enforce(r <= length,
            format("[ERROR] SegmentTree.prod: range [%s, %s) is out of range [0, %s).",
                   l, r, length));

        if (l == r) {
            return e();
        }
        if (l == 0 && r == length) {
            return node[1];
        }

        l = l + leafs;
        r = r - 1 + leafs;

        T lp = e(), rp = e();
        while (l <= r) {
            if (l % 2 == 1) {
                lp = op(lp, node[l]);
                l++;
            }
            if (r % 2 == 0) {
                rp = op(node[r], rp);
                r--;
            }

            l /= 2;
            r /= 2;
        }

        return op(lp, rp);
    }

    import std.typecons;

    Nullable!(int) maxRight (size_t l, bool delegate (T) f) {
        enforce(l < length,
            format("[ERROR] SegmentTree.maxRight: index %s is out of range [0, %s).",
                   l, length));

        Nullable!int ret;
        if (!f(get(l))) {
            return ret;
        }

        if (f(prod(l, length))) {
            ret = cast(int)(length - 1);
            return ret;
        }

        size_t cur = l + leafs;
        T val = e();
        while (f(val)) {
            if (cur % 2 == 1) {
                val = op(val, node[cur]);
                cur++;
            }
            cur /= 2;

            if (!f(op(val, node[cur]))) {
                break;
            }
        }

        while (cur < leafs) {
            if (!f(op(val, node[2 * cur]))) {
                cur = 2 * cur;
            }
            else {
                val = op(val, node[2 * cur]);
                cur = 2 * cur + 1;
            }
        }

        ret = cast(int)(cur - leafs - 1);
        return ret;
    }

    Nullable!(int) minLeft (size_t r, bool delegate (T) f) {
        enforce(r < length,
            format("[ERROR] SegmentTree.minLeft: index %s is out of range [0, %s).",
                   r, length));

        Nullable!int ret;
        if (!f(get(r))) {
            return ret;
        }

        if (f(prod(0, r + 1))) {
            ret = 0;
            return ret;
        }

        size_t cur = r + leafs;
        T val = e();
        while (f(val)) {
            if (cur % 2 == 0) {
                val = op(node[cur], val);
                cur--;
            }
            cur /= 2;

            if (!f(op(node[cur], val))) {
                break;
            }
        }

        while (cur < leafs) {
            if (!f(op(node[2 * cur + 1], val))) {
                cur = 2 * cur + 1;
            }
            else {
                val = op(node[2 * cur + 1], val);
                cur = 2 * cur;
            }
        }

        ret = cast(int)(cur - leafs + 1);
        return ret;
    }
}