結果

問題 No.3486 Draw a Rainbow
コンテスト
ユーザー 👑 binap
提出日時 2026-02-27 04:51:47
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,424 ms / 4,000 ms
コード長 2,210 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 254 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 197,632 KB
最終ジャッジ日時 2026-03-27 20:58:08
合計ジャッジ時間 26,498 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# gpt5.2で編集しました
import sys

MOD = 998244353

def main():
    input = sys.stdin.buffer.readline

    N, M, L = map(int, input().split())
    cnt = [[0] * L for _ in range(M)]

    for _ in range(N):
        A, B = map(int, input().split())
        cnt[A - 1][(B - M) - 1] += 1

    S = 1 << L
    mod = MOD

    f = [0] * S
    f[0] = 1

    POW2 = [1] * (N + 1)
    for x in range(N):
        POW2[x + 1] = (POW2[x] * 2) % mod

    for i in range(M):
        g = [0] * S
        g[0] = 1

        cnt_i = cnt[i]
        for j in range(L):
            bit = 1 << j
            t = POW2[cnt_i[j]] - 1
            if t < 0:
                t += mod

            g_old = g
            g = [0] * S

            for x, go in enumerate(g_old):
                v = g[x] + go
                if v >= mod:
                    v -= mod
                g[x] = v

                add = (go * t) % mod
                xb = x | bit
                v = g[xb] + add
                if v >= mod:
                    v -= mod
                g[xb] = v

        g[0] = 0

        # zeta transform add (f, g)
        y = 1
        while y < S:
            step = y << 1
            for base in range(0, S, step):
                end = base + y
                for x in range(base, end):
                    dst = x + y  # x|y と同じ（x&y==0 が保証される走査）
                    v = f[dst] + f[x]
                    if v >= mod:
                        v -= mod
                    f[dst] = v

                    v = g[dst] + g[x]
                    if v >= mod:
                        v -= mod
                    g[dst] = v
            y = step

        # pointwise multiply
        for x in range(S):
            f[x] = (f[x] * g[x]) % mod

        # mobius inversion
        y = 1
        while y < S:
            step = y << 1
            for base in range(0, S, step):
                end = base + y
                for x in range(base, end):
                    dst = x + y
                    v = f[dst] - f[x]
                    if v < 0:
                        v += mod
                    f[dst] = v
            y = step

    print(f[S - 1] % mod)

if __name__ == "__main__":
    main()
0